Dijkstra算法求解最短路径 自写代码
#include <iostream>
#define Max 503
#define INF 0xcffffffusing namespace std;typedef struct AMGraph { //定义图int vex, arc;int arcs[Max][Max]; //邻接矩阵
};int dist[Max], path[Max]; //dis保存最短路径总权值、path通过保存路径的前驱结点来保存路径
bool final[Max]; //已找到最短路集合int distmin(AMGraph& G) {int flag = 0;int min = INF;for (int i = 1; i <= G.vex; i++) {if (final[i] == false && min > dist[i]) {min = dist[i];flag = i;}}return flag;
}void Dijkstra(AMGraph& G,int x) //迪杰斯特拉算法
{for (int i = 1; i <= G.vex; i++) {if (i != x) dist[i] = INF;else dist[i] = 0;}memset(final, 0, sizeof(final));memset(path, -1, sizeof(path));for (int i = 1; i <= G.vex - 1; i++) {int minflag = distmin(G);final[minflag] = true;for (int j = 1; j <= G.vex; j++) {if (G.arcs[minflag][j] > 0) {if (dist[minflag] + G.arcs[minflag][j] < dist[j]) {dist[j] = dist[minflag] + G.arcs[minflag][j];path[j] = minflag;}}}}}void find(int x) //递归输出最短路径
{if (path[x] == -1) {cout << x;}else {find(path[x]);cout << " -> " << x;}return;
}void putin(AMGraph& G) //输入图
{cin >> G.vex >> G.arc;for (int i = 1; i <= G.vex; i++) //初始化邻接矩阵for (int j = 1; j <= G.vex; j++)G.arcs[i][j] = INF;for (int i = 1; i <= G.arc; i++){int u, v, w;cin >> u >> v >> w;G.arcs[u][v] = w;}
}void putout(AMGraph& G,int x) //输出
{//cout << "起点 v1 到各点的最短路程为: \n";for (int i = 1; i < G.vex; i++){cout << dist[i] << " ";}cout << dist[G.vex] << endl;for (int i = 1; i <= G.vex; i++){if (i != x) {cout << "起点 v"<<x<<" 到 v" << i << " 的路径为： ";find(i);cout <<"带权路径长度是"<< dist[i];cout << endl;}}
}int main()
{AMGraph G;putin(G);int point = 3;//要算的是point点到其他点的距离Dijkstra(G,point);putout(G,point);return 0;
}
/*测试数据，王道2025版p243的图。
5 10
1 2 10
1 5 5
2 5 2
5 2 3
2 3 1
5 3 9
5 4 2
3 4 4
4 3 6
4 1 7
*/http://t.csdnimg.cn/aaE07
http://t.csdnimg.cn/aaE07参考文章如上，另外进行了一点改进。