wordpress 回复可见河北seo网络优化师
编程要求
在图的应用中，有一个很重要的需求：我们需要知道从某一个点开始，到其他所有点的最短路径。这其中，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[n+1],将dic初始化存储从1到所有点的直接距离。比如dic[1]到dic[5]分别是【0，8，1，2，99999999】，因为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] = 99999999>dic[3]+arr[3][5] = 4,能使1到5距离缩短，于是改变dic[5]的值。这样我们就得到能通过3进行优化一轮路径，学术名叫做松弛。
我们知道，如果已经通过3实现了一轮优化，那么我们将进一步缩短路程的话，是不能走回头路的，因为如果再次经过3的话没有意义，所以最短路没有重复路径。
那么我们就要定义一个数组来存储已经作为转点进行一轮松弛的点，我们可以定义book[n+1]来存储。将作为转点的点比如3，用book[3] = 1，表示已经使用过。
之后便是重复步骤，找除去dic[3]以外的最小值，也就是dic[4],继续进行一轮松弛，将4这个点用book[4] = 1,表示已经使用过。
之后的图大家可以自己试着来画出。
具体代码：
#include<stdio.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;
}
注意：
实际上迪杰斯特拉算法可以看作是贪心算法，通过每一步的最优解组合成全局最优解，感兴趣的同学们可以去网上查找关于贪心算法的知识，这种类型的题目我们以后也会分享。