CodeFights: реализация алгоритма Дейкстры

Question

Учитывая эту проблему борьбы код:

Рассмотрим большой город, расположенный на п островах. Мосты соединяют острова, но все они имеют только одностороннее движение. Хуже того, большинство мостов закрыты ночью, поэтому на одном из островов A есть любой мост с любым движением, идущим с любого острова A.

Существует программист, который превращает пенни в рабочие ночи, водитель Uber. Однажды ночью его телефон умирает сразу после того, как он берет всадника, идущего с острова 0 на остров (n - 1). Он имеет карту городских мостов на своем ноутбуке, хотя (хранится как матрица расстояний), поэтому он решает реализовать алгоритм, который вычисляет кратчайший путь между этими двумя островами и оценивает стоимость, основанную на расстоянии пути. Предположим, что каждая миля поездки составляет 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]; 

Однако, когда я запускаю код, он проходит только 6/7 тестовые случаи (последние 3 Тестовые скрыты мне так я не знаю, что такое входы).

Может ли кто-нибудь сказать мне, что не так с моей реализацией dijkstra? Мне что-то не хватает в том, как работают дикстры?

Answer 1

Вы должны найти, что посещенный узел содержит минимальный ключ (расстояние) на каждой итерации вместо попыток всех посещенных узлов. Хотя релаксация по-прежнему безопасна, вы можете поместить некоторые из узлов, не имеющих оптимального ключа к посещенному набору, и, следовательно, компрометирует результат.

Кроме того, хотя я не думаю, что это изменит результат, было бы лучше избегать сравнения двух чисел с плавающей запятой, используя == или !=.