前面说了单源最短路径算法 Dijkstra，以及多源最短路径算法 Floyd，但是都不能适用于有负权边存在的情况，这里实现一下是西南交通大学段凡丁于 1994 年发表的 SPFA（Shortest Path Faster Algorithm）算法。该算法在 Bellman-ford 算法的基础上加上一个队列优化，减少了冗余的松弛操作。
spfa 可以适用于有负权边存在的情况，但是无法求解存在负权回路的情况，但是可以判断
原理
只要最短路径存在，SPFA 算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点 v 的最短路径估计值 d[v]变小。所以算法的执行会使 d 越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着 d 值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。
实现
github
BFS
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
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
