最短路径算法-Dijkstra

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

算法描述

这个算法是通过为每个顶点 v 保留目前为止所找到的从 s 到 v 的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0 （d[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把 d[m]设为 w（s, m）,同时把所有其他（s 不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于所有顶点的集合 V 中的任意顶点 v，若 v 不为 s 和上述 m 之一， d[v] = ∞）。当算法结束时，d[v] 中存储的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。
边的拓展是 Dijkstra 算法的基础操作：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小，我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 的最短路径的长度值。此算法的组织令 d[u] 达到其最终值时，每条边（u, v）都只被拓展一次。
算法维护两个顶点集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的顶点 v ，而集合 Q 则保留其他所有顶点。集合 S 初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对 u 的每条外接边 (u, v) 进行拓展。

如下图：

代码实现-Golang

github

package ShortestPath

import (
	"errors"

	"container/list"

	"github.com/mohuishou/algorithm/Graph"
)

//INF 无穷大
const INF = 0xffffff

//Dijkstra 算法
//一种求单源最短路径的算法
func Dijkstra(graph Graph.Graph, s Graph.VextexType, dist []Graph.EdgeType, path []Graph.VextexType) {
	visited := make([]bool, graph.VNum)
	//初始化
	for i := 0; i < graph.VNum; i++ {
		dist[i] = INF //距离为无穷大
		path[i] = -1  //没有上一个节点
		visited[i] = false
	}
	path[s] = s
	dist[s] = 0

	//使用list实现一个队列操作
	q := list.New()

	//将点s入队
	q.PushBack(s)
	for q.Len() != 0 {
		u := q.Front().Value.(Graph.VextexType)
		q.Remove(q.Front())
		//如果该点周围的点已经走过，则无需再走
		if visited[u] {
			continue
		}

		//将该点加入已观察
		visited[u] = true

		e := graph.G[u].FisrtEdge

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

			//如果该点尚未走过，并且当前点的距离加上边的距离小于之前该点的距离，那么就更新该点的距离
			if visited[v] == false && dist[v] > dist[u]+e.Weight {
				dist[v] = dist[u] + e.Weight //更新该点距离
				path[v] = u                  //更新父节点
				q.PushBack(v)                //将该点入队
			}
			e = e.Next
		}

	}

}

//GetPath 通过路径获得到指定目的节点的路径
func GetPath(path []Graph.VextexType, t Graph.VextexType) ([]Graph.VextexType, error) {
	tPath := make([]Graph.VextexType, 0)
	for {
		tPath = append(tPath, t)
		if path[t] == -1 {
			return nil, errors.New("不存在到该节点的路径")
		}
		if t == path[t] {
			return tPath, nil
		}
		t = path[t]
	}
}