最短路径算法SPFA

前面说了单源最短路径算法Dijkstra,以及多源最短路径算法Floyd,但是都不能适用于有负权边存在的情况,这里实现一下是西南交通大学段凡丁于1994年发表的SPFA(Shortest Path Faster Algorithm)算法。该算法在Bellman-ford算法的基础上加上一个队列优化,减少了冗余的松弛操作。

spfa可以适用于有负权边存在的情况,但是无法求解存在负权回路的情况,但是可以判断

原理

只要最短路径存在,SPFA算法必定能求出最小值。证明:每次将点放入队尾,都是经过松弛操作达到的。换言之,每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路,所以每个结点都有最短路径值。因此,算法不会无限执行下去,随着d值的逐渐变小,直到到达最短路径值时,算法结束,这时的最短路径估计值就是对应结点的最短路径值。

实现

github

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
q := list.New()
q.PushBack(s)

//循环跳出条件:队列为空
for q.Len() != 0 {
u := q.Front().Value.(Graph.VextexType)
q.Remove(q.Front())

//释放对点u的标记
visited[u] = false

e := graph.G[u].FisrtEdge

for e != nil {
//这条边下的顶点
v := e.V

//如果当前点的距离加上边的距离小于之前该点的距离,那么就更新该点的距离
if dist[v] > dist[u]+e.Weight {
dist[v] = dist[u] + e.Weight //更新该点距离
path[v] = u //更新父节点

//如果顶点不在队内,则将顶点入队
if visited[v] == false {
q.PushBack(v) //将该点入队
visited[v] = true
count[v]++

//出现负环,报错
if count[v] > graph.VNum {
return errors.New("存在负环!")
}
}
}
e = e.Next
}

}
return nil

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
visited[u] = true
e := graph.G[u].FisrtEdge
for e != nil {
v := e.V
if dist[v] > dist[u]+e.Weight {
dist[v] = dist[u] + e.Weight //更新该点距离
path[v] = u //更新父节点
if visited[v] == false {
count[v]++
if count[v] > graph.VNum {
return errors.New("存在负环!")
}

//注意DFS的结果不能直接return,直接return的时候回溯的时候就没有办法在上一级重新找值了
err := DFS(v)
if err != nil {
return err
}
} else {
return nil
}
}
e = e.Next
}
visited[u] = false
return nil