图论-单源最短路径算法（拓扑，Dijkstra，Floyd，SPFA）
前言
单源最短路径是学习图论算法的入门级台阶，但刚开始看的时候就蒙了，什么有环没环，有负权没负权，下面就来总结一下求单源最短路径的所有算法以及其适用的情况。
单源最短路径
设定图中一个点为源点，求其他所有点到源点的最短路径。
先声明一点：有负环的图中没有最短路径
因为负环绕一圈的权值和是负的，只要过一遍环，路径就减小，可以反复过，无限减小
1. 无环 无负权 图求单源最短路径--拓扑排序
求v到其他所有点的最短路径
归纳假设
已知v到前面n-1个点的最短路径
求n
假设每一个点带一个属性sp，表示该点到源点的最短路径长度
设第n个点为z
我们知道所有能到z的点wk，即(wk, z)是图中的边
这样求出来wk.sp + len（wk, z）的最小值
就是z的sp
为什么要拓扑排序？
拓扑排序保证看n的时候，与n连接的前面的所有点都看了
复杂度O(V + E)
伪代码：
const int MAX = MAX_INT
for(all w){
w.sp = MAX
}
init w.indegree DFS
w with 0 indegree, enqueue
while(!queue.empty()){
w = dequeue();
for(all (w, z)){
if(w.sp + len(w, z) < z.sp){
z.sp = w.sp + len(w, z);
}
z.indegree--;
if(z.indegree = 0){
z.enqueue();
}
}
}
2. 有环 无负权 图求单源最短路径--Dijkstra算法
前面拓扑排序的求所有点的最短路径只能是无环图
有环会导致拓扑排序无法终止
没法用
Dijkstra算法可以解决有环 无负权最短路径的问题
Dijkstra算法是求源点到其他所有点的最短路径
定义两个集合
一个集合是S, 表示已经确定了最短路径的点
另一堆是剩下的所有点M的集合
Init-每个点的路径长度设为无穷
每次从剩下的点中取路径长度最小的加入到S中
开始
只有源点在S中
计算源点所有连接点的路径长度
取出最小x的加入到S中
并对所有连接x的点更新路径长度
再挑出最小的
反复
直到所有点都加到S中
解决了
注意：这里与prim算法有点像
Diljstra算法是不断从剩下的点中选取路径最小的加入的S中
prim算法是不断从剩下的点中选取能到S且边的权值最小的加入到S中
伪代码：
const int MAX = MAX_INT;
for(all w except v in G){
w.sp = MAX;
w.mark = false;
}
v.sp = 0;
build a heap for all vetex;
while(there exist unmarked vertex){
w = heap.pop(); //w.sp is minimum
w.mark = true;
for(all (w, z) in G and z is unmarked){
if(w.sp + len(w, z) < z.sp){
z.sp = w.sp + len(w, z);
}
}
heapsort();
}
build the Heap // O(VlogV)
最多需要E次更新，每一次更新O(logv)
从而总时间
O((E+V)logV)
问：为什么Dijkstra算法不能求解带负权的路径的图的最短路径？
答：采用dijkstra算法处理带有负权边的图时有可能出现这样一种情况：因为dijktra算法每一次将一个节点加入已访问集合之中，之后不能在更新，
如图
算法刚开始执行时，将A添加到集合中标记已访问，之后选出从A到所有节点中的最短的d，于是把C加入集合中标记已访问，之后C不能在更新了，而显然，A与C之间最短路径权值为0（A-B-C），发生错误。
3. 有环 有负权 图的单源最短路径--Floyd算法
可以用于带负权的图
Floyd算法
动态规划
C[i][j] 表示i点到j点的最短距离
小问题可解-所有相邻的边的权值已知
大问题分解为小问题
从i到j
两种途径
1.图中有边连接i与j
2.经过k点到，C[i][j] = C[i][k] + C[k][j]
1 <= k <= N
两种的最小值就是C[i][j]
定义矩阵C[N][N]
然后不断dp
伪代码：
const int MAX = MAX_INT;
c[N][N]
for(i = 1; i <= N; i++){
for(j = 0; i <= N; j++){
if((i, j) is in G ){
c[i][j] = (i, j).weight;
}
else{
c[i][j] = MAX;
}
}
}
for(k = 1; k <= N; j++){
for(i = 1; i <= N; i++){
for(j = 0; j <= N; j++){
if(c[i][j] > c[i][k] + c[k][j]){
c[i][j] = c[i][k] + c[k][j];
}
}
}
}复杂度O(n^3)
注意k只能放在最外层的循环
不能放在最里层
若放在最里层
计算第一行eg (1, 10)时
要算(1, 5) (5, 10)
但这时(5, 10)还未知
所以确定的(1, 10)点的最短路径是不准确 的
k放最外面的循环中
保证计算每次看计算C[i][j]时， C[i][k] + C[k][j]都是已经求过的值
4. 有环 有负权 图单源最短路径算法--SPFA
带有负权的图
不能使用Dijkstra算法
floyd算法又复杂度太高
然后西安交通大学acm大牛想出了SPFA
中华少年英才多啊
SPFA
设立一个队列
d[i]表示源点到i的最短距离
init所有d[i]都为无穷
刚开始源点入队
x出队
检查x连接的所有点d[i]值,如果变小，则跟新
更新了的点y，说明与y连接的点也有可能更新
y入队
之后不断反复
因为点数有限，所以必然一定步骤后队列会为空
这时就求得了所有点的最短路径
真TMD神奇
检查每个点连接的所有点，总检查就是边数E
每个点可能入队多次，设平均入队次数为k
复杂度O(kE)
可以证明k<=2
Spfa 有两种实现方法：bfs，dfs
bfs判断起来较麻烦
得计算所有点入队的次数
如果一个点入队超过N次，一定有负环
bfs伪代码：
const int MAX = MAX_INT
spfa_bfs(){
suppose root = s;
d[N]; //The min path length of s to i
vis[N]; //1 -- i is in the queue
count[N]; //The count of i to enqueue
for(i = 1; i <= N; i++){
d[N] = MAX;
}
d[s] = 0;
vis[s] = 1;
count[s] = 1;
enqueue(s);
while(!queue.empty()){
x = dequeue();
vis[s] = 0;
for((x, y) is in G){
if(d[y] > d[x] + len(x, y)){
d[y] = d[x] + len(x, y);
vis[y] = 1;
count[y]++;
if(count[y] >= N){
return -1; // There is a minus circle
}
}
}
}
}
dfs 伪代码：
判断负环较快
vis[N]; //1 -- i is checked
int spfa_dfs(point v){
vis[v] = 1;
for((v, w) is in G){
if(d[w] > d[v] + len(v, w)){
d[w] = d[v] + len(v, w);
if(vis[w] == 0){
if(spfa_dfs(w) == -1){
return -1;
} //-1 there is a minus circle
}
else{
return -1;
}
}
}
vis[v] = 0;
}
总结
无环 无负权 图单源最短路径--拓扑排序
有环 无负权 图单源最短路径--Dijkstra算法
有环 有负权 图单源最短路径--Floyd算法
有环 有负权 图单源最短路径--SPFA
这里总结了计算单源最短路径的四种常见算法，理清楚他们分别适用的情况，以及他们之间的关系便会很好记忆。