Алгоритм Дейкстры сбой при нескольких вызовах - PullRequest
Новая
       35

Алгоритм Дейкстры сбой при нескольких вызовах

2 голосов
/ 12 июня 2019

Итак, я пишу симулятор для бизнеса по доставке пакетов и сталкиваюсь с трудностями, связанными с реализацией алгоритма Дейкстры, который я не могу точно определить.

Основная цель с помощью приведенного ниже кода заключается в создании двумерного массива кратчайших расстояний для быстрого поиска во время движения в случае возможных изменений в пункте назначения.

Массив расстояний, возвращаемый после вызова моего пути find_shortest, оставляет максимальное целочисленное значение, даже если граф полностью связан. Эта проблема возникает, когда я пытаюсь запустить его из начальной позиции> 0. 

#
# Used to define/process adjency matrices for the simulation
import sys


class DistanceTable:
    def __init__(self, size, labels):
        self.table = [[0 for column in range(size)]
                      for row in range(size)]
        self.labels = labels
        self.size = size

    def get_minimum_distance(self, distances, visited):
        prev_min = sys.maxsize
        min_distance_idx = -1
        for i in range(self.size):
            if distances[i] <= prev_min and visited[i] is False:
                prev_min = distances[i]
                min_distance_idx = i

        return min_distance_idx

    def find_shortest(self, start_val):
        visited = [False] * self.size
        distances = [sys.maxsize] * self.size
        distances[start_val] = 0

        for i in range(self.size):
            min_distance_idx = self.get_minimum_distance(distances, visited)
            visited[min_distance_idx] = True

            for y in range(self.size):
                if visited[y] is False and self.table[i][y] > 0 and distances[y] > distances[i] + self.table[i][y]:
                    distances[y] = distances[i] + self.table[i][y]

        return distances


labels = [''] * 3
size = len(labels)
distance = [[0, 2, 18],
            [1, 0, 4],
            [5, 13, 0]]

graph = DistanceTable(size, labels)
graph.table = distance

dist = [[0 for column in range(size)]
        for row in range(size)]

for i in range(3):
    dist[i] = graph.find_shortest(i)
    print(dist[i])

Это наименьшее, что я мог бы сделать в этом примере, и результат отпечатков выше: 

[0, 2, 6]
[1, 0, 9223372036854775807]
[9223372036854775807, 9223372036854775807, 0]

Или для удобства чтения 

[0,         2,           6         ]
[1,         0,           sys.maxint]
[sys.maxint, sys.maxint, 0         ]
...