注意Dijkstra不能处理带负权的图，若带负权请使用spfa外加判断各点入队的次数。
Dijkstra的过程跟之前我写过的Prim最小生成树的算法很类似，貌似没差别。当边不是很密集的时候bfs就可以搞定，当边比较多时Dijkstra比较稳定。所以对于边密集类型用常用邻接矩阵来存图，vis【】数组来判定到达某点的最短路径是否已经确定（有点像Prim中判断点是否进入树中），起点必然是确定的，接着桶排思想枚举剩下的点找到到已经确定的点的区域（类似Prim中的树）距离最短的点，标记进入确定最短的点集，由于新点的加入，再枚举一次剩下的点，更新到这个新生成的点域的最小距离。总上为一个大循环（每次大循环结束确定一个新的点，故循环N-1次），两个内嵌的小循环，跟Prim一毛一样~。所以其实最小生成树就是一个图单源最短路径的一个体现（个人见解，若有不当欢迎指正）。
#define Inf 0x3f3f3f3f const int maxn = 1e3 + 2; int dis[maxn], table[maxn][maxn], N; bool vis[maxn]; //记录是否已经找到达该点的最小值 void dijkstra() { for(int i=1; i<=N; ++i) dis[i] = table[i][s]; dis[1] = 0; memset(vis, false, sizeof(vis)); vis[s] = true; for(int i=1; i<=N; ++i){ int index = -1, mindis = Inf; for(int j=1; j <= N; ++j){ if(!vis[j] && dis[j] < mindis){ mindis = dis[j]; index = j; } } if(index = -1) break; //最短路不存在 vis[index] = true; for(int j=1; j<=N; ++j){ if(dis[j] > dis[index] + table[index][j] && !vis[j]) dis[j] = dis[index] + table[index][j]; } } return; }
原文：https://www.cnblogs.com/GorgeousBankarian/p/11147296.html