CodeFights：ダイクストラのアルゴリズムの実装

Question

このコードの戦いの問題を考慮すると：

は、n個の島に位置大都市を考えてみましょう。島を結ぶ橋がありますが、それらはすべて一方通行しかありません。事態を悪化させるために、ほとんどの橋は夜間に閉鎖されているので、島Aから他の島Bへの橋渡しはほとんどありません。

夜間の作業でペニーを変えるプログラマがいますUberのドライバー。ある夜、島0から島（n - 1）に向かうライダーを迎えた直後に電話が切れる。彼はラップトップに都市の橋の地図を持っていますが（距離のマトリックスとして保存されているので）、それらの2つの島の間の最短経路を計算し、経路の距離に基づいてコストを評価するアルゴリズムを実装することにします。旅行の各マイルは1 $と仮定する。

私はそれを解決するためにダイクストラのアルゴリズムを実装することを決定した：私は、コードを実行すると

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]; 

はしかし、それだけで、最後の3のテストケースがそのように私に隠されている（6/7テストケースに合格私は入力が何であるか分からない）。

dijkstraの実装で何が問題なのか教えていただけますか？ dijkstrasの仕組みに何か不足していますか？

Answer 1

訪問先ノードには、訪問したすべてのノードを試行する代わりに、各繰り返しで最小のキー（距離）が含まれているはずです。リラクゼーションはまだ安全ですが、ビジターセットに最適なキーを持たないノードのいくつかを配置して、結果を損なう可能性があります。

さらに、結果が変わるとは思わないが、==または!=を使用して2つの浮動小数点数を比較しないほうがよいでしょう。