C++实现Dijkstra算法

1、原理步骤2、举例3，代码实现

1、原理步骤

1，找出源点v0到其他各点的直达路径，将其记录在dist数组中,dist[i]表示从v0到vi的距离。若从v0到vi无法直达，则将dist[i]记为无穷大Max。

2，找出dist数组中未被访问过且与v0之间距离最短的点u。

3，通过u来更新dist数组，若从v0经过u再到达vi的距离比dist[i]要小，则将dist[i]更新为dist[u]+edge[u][i];

4，继续2，3步骤，共进行n-1次，此时dist[i]表示从v0到vi的最短距离。

2、举例

如图，求v0到其他点的最短路径。先初始化dist数组，dist[1] = 13, dist[2] = 18, dist[3] = Max, dist[4] = 30, dist[5] = Max, dist[6] = 32;

寻找最短边，为dist[2]=8,比较从v0到vi和从v0经过v2再到vi的距离大小，更新dist[i], 因为 dist[2] + edge[2][3] = 8 + 5 = 13 < dist[3] = Max, 所以 dist[3] 更新为 13。

继续寻找最短边，为dist[1] = 13, 比较从v0到vi和从v0经过v1再到vi的距离大小，更新dist[i], 因为 dist[1] + edge[1][5] = 13 +9 = 22 < dist[5] = Max, 所以dist[5]更新为 22。同理， dist[6] 更新为 20;

继续操作至n-1次，算法结束。

3，代码实现

#include<iostream> using namespace std; #define Max 9999 int n, m; bool visited[Max]; int edge[Max][Max]; int dist[Max]; void Dijkstra() { visited[0] = true; int min = Max; int index = 0; for (int i = 0; i < n-1; ++i) { min = Max; for (int j = 0; j < n; ++j) { if (!visited[j] && dist[j] < min) //寻找最短边 { min = dist[j]; index = j; } } visited[index] = true; for (int j = 0; j < n; ++j) { if (!visited[j] && dist[index] + edge[index][j] < dist[j]) //比较从v0经过u再到达vi的距离和dist[i]的大小 { dist[j] = dist[index] + edge[index][j]; } } } for (int i = 1; i < n; ++i) { cout << dist[i] << " "; } } int main() { cout << "输入节点数: "; cin >> n; cout << "输入边数："; cin >> m; fill(edge[0], edge[0] + Max*Max, Max); //初始化各个数组 fill(dist, dist + n, Max); fill(visited, visited + n, false); int u, v, w; cout << "输入各条边的信息：" << endl; for (int i = 0; i < m; ++i) { cin >> u >> v >> w; edge[u][v] = edge[v][u] = w; } dist[0] = 0; for (int i = 1; i < n; ++i) //初始化从v0到其他各点的距离 { dist[i] = edge[0][i]; } Dijkstra(); return 0; }

输入输出信息：