Проблема алгоритма Дейкстры и ключевая ошибка в питоне

Question

Попытка кодировать алгоритм Дейкстры из этого псевдокода:

1: procedure ShortestPath
2:   for 0 ≤ i ≤ n do
3:     L(vi) = ∞
4:   end for
5:   L(a) = 0
6:   S = ∅
7:   while z /∈ S do
8:     u = vertex not in S with L(u) minimal
9:     S = S ∪ {u}
10:    for v /∈ S do
11:      if L(u) + µ(uv) < L(v) then
12:        L(v) = L(u) + µ(uv)
13:      end if
14:    end for
15:  end while
16:  return L(z)
17: end procedure

Код, который я написал, таков:

from math import inf
def dijkstras(G,start,stop):
    L = {}
    for i in G[0]:
        L[i] = inf
    L[start] = 0
    visited = []
    print(L)
    while stop not in  visited:
        u = inf
        for i in L:
            if L[i] < u and L[i] not in visited:
                u = L[i]
                break
        visited.append(u)
        for v in G[0]:
            if v in visited:
                continue

            if {u,v} or {v,u} in G[1]:
                for i in G[1]:
                    if {u,v} or {v,u} == i[0]:
                        weight = i[1]
                        break
                    else:
                        weight = inf
                if L[u] + weight < L[v]:
                    L[v] = L[u] + weight
    return stop

Это дает мне KeyError = 0, я предполагаю, что это связано со строкой L [v] = L [u] + weight. Кроме этого я думаю, что код правильный. Если кто-то обнаружит проблему, пожалуйста, дайте мне знать, ура.

Answer 1

В вашем коде я вижу u = inf or u = L[...], но в оригинальном псевдокоде u - это вершина графа, а не вес. Другими словами, вы перепутали расстояния с вершинами. Возможно использовать строки для именования вершин?

Приведите пример формата вашего графика. Является ли G [1] словарём с клавишами перехода? список пар перехода с его весом? Похоже, в другом месте это интерпретируется по-разному.

{u,v} or {v,u} == i[0], очевидно, ошибка, вы, вероятно, имели в виду {u,v} == i[0] or {v,u} == i[0]