Dijkstra在python中的算法

我想在我的python代碼上實現Dijkstra的算法，但我不能真正得到正確的算法。我使用的算法與此YouTube鏈接：https://www.youtube.com/watch?v=pVfj6mxhdMw Dijkstra在python中的算法

所以基本上我的類有這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

我沒有真正完成，因爲我知道我錯過了什麼地方的東西。有人可以幫助我這個。謝謝

來源

2016-11-29 Kumayl Fazal

維基百科：[Dijkstra算法]（https://en.wikipedia.org/wiki/Dijkstra's_algorithm）。甚至有僞碼。 – furas

你問題解決了嗎？ – Shasha99

@ Shasha99沒有。我似乎無法得到正確的算法。以前的評論沒有幫助，有人讓我找到了另一種算法，它不是真正的答案，而第二種算法讓我引發了一個hello world程序。 –

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)

來源

2016-12-01 22:47:31

Dijkstra在python中的算法

回答

相關問題