Dijkstra的python算法

本文介绍了Dijkstra的python算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试在自己的python代码上实现Dijkstra的算法，但我无法真正正确地实现该算法。我正在使用的算法来自以下youtube链接： www.youtube/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: www.youtube/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)