Dijkstraのアルゴリズム（Pythonで）

Question

私はPythonコードでDijkstraのアルゴリズムを実装しようとしていますが、実際にはアルゴリズムを正しく取得できません。私が使っているアルゴリズムは、このユーチューブのリンクからです：https://www.youtube.com/watch?v=pVfj6mxhdMw

だから基本的に私のクラスでは、これら3つの変数があります。ここでは

self.nodes = [] #a,b,c 
self.neighbours = {} # a:[b,c], b:[c], c:[a] 
self.weights = {} #[a,b] = 2, [a,c] = 5 

は、私は部分的にビデオで提供するアルゴリズムを使用して、私の最短経路の機能を実装する方法です。

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 

私はどこかで何かを逃していることを知っているので、私は本当に完了しません。誰かがこれで私を助けてくださいできますか？ありがとう

Answer 1

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)