Dijkstra算法

Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

dijkstra算法是解决带权重的单元最短路径问题,要求权重是非负，和Bellman-Ford算法很像，但是不一样，注意Bellman-Ford算法是可以处理负边，但是Dijkstra不可以

代码如下

#include <iostream> #include <vector> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <stack> #include <string> #include <climits> #include <algorithm> #include <sstream> #include <functional> #include <bitset> #include <numeric> #include <cmath> #include <regex> #include <iomanip> #include <cstdlib> #include <ctime> using namespace std; //dijkstra 是解决带权重的单元最短路径问题,要求权重是非负 const int MAX = 1000000; /* 6 个节点 1000000 1000000 10 100000 30 100 1000000 1000000 5 1000000 1000000 1000000 1000000 1000000 1000000 50 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10 1000000 1000000 1000000 20 1000000 60 1000000 1000000 1000000 1000000 1000000 1000000 结果 D[0] D[1] D[2] D[3] D[4] D[5] 0 1000000 10 50 30 60 //节点0到节点5的最短路径是0 4 3 5 */ void dijkstra() { const int n = 6; int mat[6][6] = { 0, 1000000, 10, 1000000, 30, 100, 1000000, 0, 5, 1000000, 1000000, 1000000, 1000000, 1000000, 0, 50, 1000000, 1000000, 1000000, 1000000, 1000000, 0, 1000000, 10, 1000000, 1000000, 1000000, 20, 0, 60, 1000000, 1000000, 1000000, 1000000, 1000000, 0 }; //初始化部分,dis[n]表示源节点0到其余节点的最短距离 int dis[n] = { 0 }; //前驱节点设置 int pre[n] = { 0 }; //访问标志 int visit[n] = { 0 }; //dis初始化 for (int i = 0; i<n; i++) { //前驱节点初始化,-1表示无前驱 dis[i] = mat[0][i]; if (dis[i] == MAX) pre[i] = -1; else pre[i] = 0; } pre[0] = -1; //源节点0的初始化 visit[0] = 1; //由于源节点0已经处理过了,所以处理其余的n-1个节点,也就是循环n-1次 for (int i = 1; i<n; i++) { int minDis = MAX; int tmp = 0; //选择未访问过的节点中距离最短的 for (int j = 0; j<n; j++) { if (visit[j] == 0 && dis[j] < minDis) { tmp = j; minDis = dis[j]; } } //加入访问 visit[tmp] = 1; //松弛更新 for (int j = 0; j<n; j++) { if (visit[j] == 0 && minDis + mat[tmp][j] < dis[j]) { dis[j] = minDis + mat[tmp][j]; pre[j] = tmp; } } } for (int i = 0; i<n; i++) cout << dis[i] << " "; cout << endl; //可以打印每一个节点到源节点0的最短路径的节点信息 //下面是打印节点0到-1的最短路径信息 int i = n - 1; while (i != -1) { cout << i << " "; i = pre[i]; } } int main() { dijkstra(); system("pause"); }