CodeFights：Dijkstra算法實現

Question

考慮這個代碼鬥爭問題：

考慮位於n個島一個大城市。有連接島嶼的橋樑，但它們都只有單向交通。更糟糕的是，大多數橋樑在晚上都是封閉的，所以最多隻有一座橋從任何島A到任何其他島B進行交通。

有一位程序員在夜間工作時變成一分錢一位優步車手。有一天晚上，他的電話在他從一個島嶼到另一個島嶼（n-1）上接電話後立即死亡。他在筆記本電腦中有城市橋樑的地圖（存儲爲距離矩陣），因此他決定實施一種算法，計算這兩個島之間的最短路徑，並根據路徑距離評估成本。假定旅程的每一英里是1美元。

我已經決定實施Dijkstra算法來解決這個問題：

def nightRoute(city): 
    visited = []; 
    visited.append(0); 
    distance = []; 
    for x in range(0, len(city)): 
     distance.append(float("inf")); 
    distance[0] = 0; 

    while(len(visited) != len(city)): 
     for i in visited: 
      print visited; 
      min = float("inf"); 
      minNode = -1; 
      for j in range(0, len(city)): 
       if (j not in visited and city[i][j] != -1): 
      if distance[j] > distance[i] + city[i][j]: 
      distance[j] = distance[i] + city[i][j] 
        if distance[i] + city[i][j] <= min: 
         min = distance[i] + city[i][j]; 
         minNode = j 
      if(min != float("inf") and minNode != -1): 
       visited.append(minNode); 
    return distance[len(city)-1]; 

然而，當我運行的代碼，它只是通過6/7測試用例（最後3測試用例隱藏我這麼我不知道輸入是什麼）。

有誰能告訴我我的dijkstra的實現有什麼問題嗎？我在dijkstras如何工作中錯過了一些東西？

Answer 1

您應該發現訪問節點在每次迭代中包含最小密鑰（距離），而不是嘗試所有訪問的節點。儘管放鬆仍是安全的，但您可能會將一些沒有最佳密鑰的節點放置到訪問集合中，從而影響結果。

此外，雖然我不認爲這會改變結果，但最好避免使用==或!=來比較兩個浮點數。