最短路径算法SPFA

注：本文已发布超过一年，请注意您所使用工具的相关版本是否适用

前面说了单源最短路径算法 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