Dijkstra的最短路径算法

大家好，又见面了，我是你们的朋友全栈君。

给定图中的图形和源顶点，找到给定图形中从源到所有顶点的最短路径。
Dijkstra的算法与最小生成树的Prim算法非常相似。与Prim的MST一样，我们以给定的源为根生成SPT（最短路径树）。我们维护两组，一组包含最短路径树中包含的顶点，另一组包括最短路径树中尚未包括的顶点。在算法的每个步骤中，我们找到一个顶点，该顶点位于另一个集合中（尚未包括的集合）并且与源具有最小距离。

下面是Dijkstra算法中用于查找给定图形中从单个源顶点到所有其他顶点的最短路径的详细步骤。
算法
1）创建一个集sptSet（最短路径树集），它跟踪最短路径树中包含的顶点，即，计算并最终确定与源的最小距离。最初，这个集合是空的。
2）为输入图中的所有顶点指定距离值。将所有距离值初始化为INFINITE。将源顶点的距离值指定为0，以便首先拾取它。
3）虽然sptSet不包括所有顶点
… .a）选择sptSet中不存在的顶点u并且具有最小距离值。
… .b）将你包括在sptSet中。
… .c）更新u的所有相邻顶点的距离值。要更新距离值，请遍历所有相邻顶点。对于每个相邻顶点v，如果u（来自源）和边缘u-v的权重的距离值之和小于v的距离值，则更新v的距离值。

让我们通过以下示例来理解：

set sptSet最初为空，分配给顶点的距离为{0，INF，INF，INF，INF，INF，INF，INF}，其中INF表示无穷大。 现在选择具有最小距离值的顶点。 拾取顶点0，将其包含在sptSet中。 因此sptSet变为{0}。 将0包括到sptSet后，更新其相邻顶点的距离值。 相邻的0的顶点是1和7.距离值1和7更新为4和8.在子图显示顶点及其距离值之后，仅显示具有有限距离值的顶点。 SPT中包含的顶点以绿色显示。

选择具有最小距离值的顶点并且尚未包含在SPT中（不在sptSET中）。 拾取顶点1并将其添加到sptSet。 所以sptSet现在变为{0,1}。 更新相邻顶点的距离值1.顶点2的距离值变为12。

选择具有最小距离值的顶点并且尚未包含在SPT中（不在sptSET中）。 选择顶点7。 因此sptSet现在变为{0,1,7}。 更新相邻顶点7的距离值。顶点6和8的距离值变为有限（分别为15和9）。

选择具有最小距离值的顶点并且尚未包含在SPT中（不在sptSET中）。 选择顶点6。 所以sptSet现在变成{0,1,7,6}。 更新相邻顶点的距离值6.更新顶点5和8的距离值。

我们重复上述步骤，直到sptSet不包含给定图形的所有顶点。 最后，我们得到以下最短路径树（SPT）。

我们使用布尔数组sptSet []来表示SPT中包含的顶点集。 如果值sptSet [v]为真，则顶点v包含在SPT中，否则不包括。 Array dist []用于存储所有顶点的最短距离值。

# Python program for Dijkstra's single 
# source shortest path algorithm. The program is 
# for adjacency matrix representation of the graph 

# Library for INT_MAX 
import sys 

class Graph(): 

	def __init__(self, vertices): 
		self.V = vertices 
		self.graph = [[0 for column in range(vertices)] 
					for row in range(vertices)] 

	def printSolution(self, dist): 
		print "Vertex tDistance from Source"
		for node in range(self.V): 
			print node,"t",dist[node] 

	# A utility function to find the vertex with 
	# minimum distance value, from the set of vertices 
	# not yet included in shortest path tree 
	def minDistance(self, dist, sptSet): 

		# Initilaize minimum distance for next node 
		min = sys.maxint 

		# Search not nearest vertex not in the 
		# shortest path tree 
		for v in range(self.V): 
			if dist[v] < min and sptSet[v] == False: 
				min = dist[v] 
				min_index = v 

		return min_index 

	# Funtion that implements Dijkstra's single source 
	# shortest path algorithm for a graph represented 
	# using adjacency matrix representation 
	def dijkstra(self, src): 

		dist = [sys.maxint] * self.V 
		dist[src] = 0
		sptSet = [False] * self.V 

		for cout in range(self.V): 

			# Pick the minimum distance vertex from 
			# the set of vertices not yet processed. 
			# u is always equal to src in first iteration 
			u = self.minDistance(dist, sptSet) 

			# Put the minimum distance vertex in the 
			# shotest path tree 
			sptSet[u] = True

			# Update dist value of the adjacent vertices 
			# of the picked vertex only if the current 
			# distance is greater than new distance and 
			# the vertex in not in the shotest path tree 
			for v in range(self.V): 
				if self.graph[u][v] > 0 and sptSet[v] == False and
				dist[v] > dist[u] + self.graph[u][v]: 
						dist[v] = dist[u] + self.graph[u][v] 

		self.printSolution(dist) 

# Driver program 
g = Graph(9) 
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], 
		[4, 0, 8, 0, 0, 0, 0, 11, 0], 
		[0, 8, 0, 7, 0, 4, 0, 0, 2], 
		[0, 0, 7, 0, 9, 14, 0, 0, 0], 
		[0, 0, 0, 9, 0, 10, 0, 0, 0], 
		[0, 0, 4, 14, 10, 0, 2, 0, 0], 
		[0, 0, 0, 0, 0, 2, 0, 1, 6], 
		[8, 11, 0, 0, 0, 0, 1, 0, 7], 
		[0, 0, 2, 0, 0, 0, 6, 7, 0] 
		]; 

g.dijkstra(0); 

# This code is contributed by Divyanshu Mehta 

Notes:

1）代码计算最短距离，但不计算路径信息。我们可以创建一个父数组，在更新距离时更新父数组（如prim的实现），并使用它显示从源到不同顶点的最短路径。

2）代码用于无向图，同样的dijkstra函数也可用于有向图。

3）代码找到从源到所有顶点的最短距离。如果我们只对从源到单个目标的最短距离感兴趣，当拾取的最小距离顶点等于目标时，我们可以打破循环（算法的步骤3.a）。

4）实现时间复杂度为O（V ^ 2）。如果使用邻接列表表示输入图，则可以借助二进制堆将其缩减为O（E log V）。请参阅
Dijkstra的邻接列表表示算法更多细节。

5）Dijkstra的算法不适用于具有负权重边的图。对于具有负权重边的图，可以使用Bellman-Ford算法，我们很快将其作为单独的帖子进行讨论。

Dijkstra的邻接表表示算法

Dijkstra最短路径算法中的打印路径

Dijkstra在STL中使用set的最短路径算法