python - dijkstra 算法多次调用失败

Question

因此，我正在为包裹递送业务编写一个模拟器，但我在实现 dijkstra 算法时遇到了障碍，我似乎无法确定。

以下代码的主要目标是构建一个最短距离的二维数组，以便在驾驶时快速查找目的地，以防目的地可能发生变化。

即使图形完全连接，调用我的 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         ]

标签： pythonpython-3.xalgorithmdijkstra