网站工程师培训,外贸网站 栏目,商业网站建设案例课程,北京网站建设中企云达编程要求
在图的应用中#xff0c;有一个很重要的需求#xff1a;我们需要知道从某一个点开始#xff0c;到其他所有点的最短路径。这其中#xff0c;Dijkstra 算法是典型的最短路径算法。
本关的编程任务是补全右侧代码片段中 Begin 至 End 中间的代码#xff0c;实现 …编程要求
在图的应用中有一个很重要的需求我们需要知道从某一个点开始到其他所有点的最短路径。这其中Dijkstra 算法是典型的最短路径算法。
本关的编程任务是补全右侧代码片段中 Begin 至 End 中间的代码实现 Dijkstra 算法求单源最短路径具体要求如下
补全代码 int[] Paths(int source) 方法实现 Dijkstra 算法
输出源点 source 到其他各个定点的距离如果不可达则距离输出 INF。
测试举例 测试过程
平台将创建用户补全后的ShortestPath类的对象
调用对象的addEdge(int u, int v, int w)方法添加边和边的权重信息构建图G
调用对象的Paths(int source)方法执行Dijkstra算法求最短路径并输出返回的最短路径这里源点设置为1
接着根据程序的输出判断程序是否正确。
以下是测试样例
测试输入
5 7 1 2 8 1 3 1 1 4 2 3 4 2 2 4 3 3 5 3 4 5 3 (5 和 7 分别表示顶点数和边数)
预期输出
0 5 1 2 4
思路解析 求单源最短路径就是求一个点到除它以外所有点的最短距离首先我们还是用邻接矩阵来储存图的信息。以测试输入为例示意图如下。 既然是求1的单源最短路径那我们就定义一个数组dic[n1],将dic初始化存储从1到所有点的直接距离。比如dic[1]到dic[5]分别是【081299999999】因为1无法直接到5所以初始化为99999999。 然后找出dic里面1到2-n之间的最短距离发现是dic[3] 1,然后找1通过3能到达的地方发现能到达4和5如果1通过3到达4的话得出dic[4] 2 dic[3]arr[3][4] 3无法使到四的路程更短所以不改变dic[4]的值但是我们发现到达5即dic[5] 99999999dic[3]arr[3][5] 4,能使1到5距离缩短于是改变dic[5]的值。这样我们就得到能通过3进行优化一轮路径学术名叫做松弛。 我们知道如果已经通过3实现了一轮优化那么我们将进一步缩短路程的话是不能走回头路的因为如果再次经过3的话没有意义所以最短路没有重复路径。 那么我们就要定义一个数组来存储已经作为转点进行一轮松弛的点我们可以定义book[n1]来存储。将作为转点的点比如3用book[3] 1表示已经使用过。 之后便是重复步骤找除去dic[3]以外的最小值也就是dic[4],继续进行一轮松弛将4这个点用book[4] 1,表示已经使用过。 之后的图大家可以自己试着来画出。 具体代码
#includestdio.h
int main(void)
{ int arr[100][100] { 0 }; int dic[100]; int book[100] { 0 }; int m, n, a, b, c, u, v; int inf 99999999; scanf(%d%d, n, m); for (int i 1; i n; i) for (int j 1; j n; j) if (i j) arr[i][j] 0; else arr[i][j] inf; for (int i 1; i m; i) { scanf(%d%d%d, a, b, c); arr[a][b] c; arr[b][a] c; }//无向图初始化。 for (int i 1; i n; i) dic[i] arr[1][i];//初始化dic数组 for (int i 1; i n - 1; i)//最多要进行n-1轮松弛i值不会使用仅仅表示循环多少轮。 { int min inf; for (int j 2; j n; j) { if (book[j] 0 dic[j] min) { min dic[j]; u j; } }//找出从1到任意数字的最短值。 book[u] 1;//将该位置提前存储表示已经使用过。 for (v 2; v n; v)//优化1通过u到所有点的路径。 { if (arr[u][v] inf)//如果u到v没有通路也就没办法优化。 { if (dic[v] dic[u] arr[u][v]) dic[v] dic[u] arr[u][v];//优化赋值过程。 } } } for (int i 1; i n; i) printf(%d , dic[i]);//打印结果。 return 0;
} 注意 实际上迪杰斯特拉算法可以看作是贪心算法通过每一步的最优解组合成全局最优解感兴趣的同学们可以去网上查找关于贪心算法的知识这种类型的题目我们以后也会分享。
