最短路径算法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

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!