Dijkstra的python算法 [英] Dijkstra’s Algorithm in python
本文介绍了Dijkstra的python算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在尝试在自己的python代码上实现Dijkstra的算法,但我无法真正正确地实现该算法。我正在使用的算法来自以下youtube链接: https://www.youtube.com/watch ?v = pVfj6mxhdMw
I am trying to implement Dijkstra’s algorithm on my python code but I can't really get the algorithm right. The algorithm I am using is from this youtube link: https://www.youtube.com/watch?v=pVfj6mxhdMw
所以基本上我的班级有以下3个变量:
So basically my class has these 3 variables:
self.nodes = [] #a,b,c
self.neighbours = {} # a:[b,c], b:[c], c:[a]
self.weights = {} #[a,b] = 2, [a,c] = 5
以下是我使用视频中提供的算法部分实现最短路径功能的方法:
Here is how I partially implemented my shortest path function using the algorithm provided in the video:
def dijkstra(self, start, end):
nodes = {}
for n in self.nodes:
if n == start:
nodes[n] = 0
else:
nodes[n] = float('inf')
unvisited = self.neighbours
visited = []
current_node = start
current_distance = 0
while unvisited:
for n in unvisited[current_node]:
print(n)
#calc_weight = nodes[n] + self.weights[n, current_node]
#if (unvisited[n] is None or calc_weight > nodes[n]):
#nodes[n] = calc_weight
visited.append(current_node)
del unvisited[current_node]
if not unvisited: break
我还没有真正完成,因为我知道我在某处错过了一些东西。有人可以帮我吗谢谢
I havent really completed because I know I missing something out somewhere. Can someone please help me with this. Thank you
推荐答案
def dijkstra(self, start, end):
nodes = self.neighbours #{'A': {'B':2}, 'B': {'C':4}, ... }
unvisited = {n: 1000 for n in self.nodes} #unvisited node & distance
unvisited[start] = 0 #set start vertex to 0
visited = {} #list of all visited nodes
parent = {} #predecessors
while unvisited:
min_node = min(unvisited, key=unvisited.get) #get smallest distance
for neighbour in nodes[min_node].items():
if neighbour not in visited:
new_distance = unvisited[min_node] + nodes[min_node][neighbour]
if new_distance < unvisited[neighbour]:
unvisited[neighbour] = new_distance
parent[neighbour] = min_node
visited[min_node] = unvisited[min_node]
unvisited.pop(min_node)
print(parent, visited)
这篇关于Dijkstra的python算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文