python - Dijkstra 在 Python 中的算法实现 - 它是如何工作的?
问题描述
我可以使用以下英文算法在纸上使用 Dijkstra 算法找到最短路径:
第 1 步:为起始节点分配永久标签和顺序
步骤2:为起始节点直接到达的所有节点分配临时标签
步骤 3:选择最低的临时标签并使其永久化
第 4 步:为节点分配订单
步骤 5:为从新永久节点直接到达的节点更新和分配临时标签
第 6 步:重复第 3、4 和 5 步,直到目标节点成为永久节点
我搜索了一个 Python 实现,其中许多都非常复杂或使用我不熟悉的数据结构。最后我找到了下面的那个。我花了相当长的时间在 Python 可视化器中跟踪它的执行情况,我可以了解它是如何工作的,但我还没有点击它。
有人可以解释一下代码与英文算法的关系吗?例如,“前辈”的概念与英文版中的“永久标签”有何关系?
from math import inf
graph = {'a':{'b':10,'c':3},'b':{'c':1,'d':2},'c':{'b':4,'d':8,'e':2},'d':{'e':7},'e':{'d':9}}
def dijkstra(graph,start,goal):
shortest_distance = {}
predecessor = {}
unseenNodes = graph
infinity = inf
path = []
for node in unseenNodes:
shortest_distance[node] = infinity
shortest_distance[start] = 0
# Determine which is minimum node. What does that mean?
while unseenNodes:
minNode = None
for node in unseenNodes:
if minNode is None:
minNode = node
elif shortest_distance[node] < shortest_distance[minNode]:
minNode = node
for edge, weight in graph[minNode].items():
if weight + shortest_distance[minNode] < shortest_distance[edge]:
shortest_distance[edge] = weight + shortest_distance[minNode]
predecessor[edge] = minNode
unseenNodes.pop(minNode)
currentNode = goal
while currentNode != start:
try:
path.insert(0,currentNode)
currentNode = predecessor[currentNode]
except KeyError:
print('Path not reachable')
break
path.insert(0,start)
if shortest_distance[goal] != infinity:
print('Shortest distance is ' + str(shortest_distance[goal]))
print('And the path is ' + str(path))
dijkstra(graph, 'a', 'b')
解决方案
Dijkstra 的算法与 prim 的最小生成树算法相同。像 Prim 的 MST 一样,我们生成一个以给定源为根的最短路径树。我们维护两组,一组包含包含在最短路径树中的顶点,另一组包含尚未包含在最短路径树中的顶点。在算法的每一步,我们都会找到一个顶点,该顶点在另一个集合(尚未包含的集合)中,并且与源的距离最小。
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])
def minDistance(self, dist, sptSet):
min = sys.maxint
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v
return min_index
def dijkstra(self, src):
dist = [sys.maxint] * self.V
dist[src] = 0
sptSet = [False] * self.V
for cout in range(self.V):
u = self.minDistance(dist, sptSet)
sptSet[u] = True
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)
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)
推荐阅读
- java - Thymeleaf:EL1043E:意外的令牌
- android - 使用 Glide、Picasso、Coli、Fresco 加载图像时出错
- c# - 大约 3 秒后,被摧毁的子弹不会克隆和射击
- .net - 使用 ACE OLEDB 将数据导出到模板化 xls 文件时,视图会受到影响
- go - 围绕 logrus 创建一个包装器接口
- java - 为 ADF 中的下拉菜单设置默认值
- laravel-8 - Laravel 帆命令除了上帆和下帆没有任何反应
- google-apps-script - 自动填充公式(跨电子表格运行) - Google 表格/应用程序脚本
- flutter - 如何创建通过图标显示所选项目的自定义下拉列表?
- wordpress - 将多站点 Wordpress 应用程序重新托管为另一个托管服务中的单独站点