python - Dijkstra 的最短路径

Question

我对 Python 非常陌生（自学）并且正在编写一些代码，并且已经尽可能多地阅读（在这个网站和 youtube 上）来弄清楚它，我很困惑为什么它不适合我

我已经生成了这本词典词典（可能不是最有效的，请让我知道如何改进，只做了几个星期）：

graphx = []
all_locs = []
def graph(width, height):
    for r in range(height):
        row = []
        for c in range(width):
            t = (r, c)
            row.append(t)
            all_locs.append(t)
        graphx.append(row)
graph(width, height)

# # Builds a dictionary of all nodes, and their weight
weighted_grid = {}
for node in graphx:
    for c in node:
        n = {}
        s = {}
        e = {}
        w = {}
        if (c[0] < height) and (c[0] > 0):
            n[c[0] + 1, c[1]] = 1
            s[c[0] - 1, c[1]] = 1
        elif c[0] == 0:
            n[c[0] + 1, c[1]] = 1
        elif c[0] == height:
            s[c[0] - 1, c[1]] = 1
        if c[1] < width and c[1] > 0:
            e[c[0], c[1] + 1] = 1
            w[c[0], c[1] - 1] = 1
        elif c[1] == 0:
            e[c[0], c[1] + 1] = 1
        elif c[1] == height:
            w[c[0], c[1] - 1] = 1
        temp = {}
        blank = {}
        if n != blank:
            temp[c[0] + 1, c[1]] = 1
        if e != blank:
            temp[c[0], c[1] + 1] = 1
        if s != blank:
            temp[c[0] - 1, c[1]] = 1
        if w != blank:
            temp[c[0], c[1] - 1] = 1
        weighted_grid[c[0],c[1]] = temp

当我运行 dijikstras 时，使用元组作为起点和终点，我得到一个错误。这是我正在运行的 dijkstras 版本：

def dijkstra(graph, start, goal):
shortest_distance = {}  # records the current cost to reach that node.
track_predecessor = {}  # keeps track of the path that led to this node.
unseen_nodes = graph    # Iterate through the graph to check all nodes.
infinity = 99999        # Make it any large number,greater than possible path weights.
track_path = []               # gives us the trace-back path of the optimal route

for node in unseen_nodes:
    shortest_distance[node] = infinity
shortest_distance[start] = 0

while unseen_nodes:

    min_distance_node = None
    for node in unseen_nodes:
        if min_distance_node is None:
            min_distance_node = node
        elif shortest_distance[node] < shortest_distance[min_distance_node]:
            min_distance_node = node

    path_options = graph[min_distance_node].items()

    for child_node, weight in path_options:

        if weight + shortest_distance[min_distance_node] < shortest_distance[child_node]:
            shortest_distance[child_node] = weight + shortest_distance[min_distance_node]
            track_predecessor[child_node] = min_distance_node

    unseen_nodes.pop(min_distance_node)

current_node = goal
while current_node != start:
    try:
        track_path.insert(0, current_node)
        current_node = track_predecessor[current_node]
    except KeyError:
        break
track_path.insert(0, start)

if shortest_distance[goal] != infinity:
    pass

我得到的错误是：

Traceback (most recent call last):
  File "C:/Users/Dave/Desktop/Important/PycharmProjects/DMT2/dungeonmasterstome/Main.py", line 318, in <module>
    dijkstra(weighted_grid, (0, 0), (0,1))
  File "C:/Users/Dave/Desktop/Important/PycharmProjects/DMT2/dungeonmasterstome/Main.py", line 300, in dijkstra
    if weight + shortest_distance[min_distance_node] < shortest_distance[child_node]:
KeyError: (0, 30)

想法和感谢任何帮助和建设性的批评。

标签： python