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