Reputation: 53
Trying to code Dijkstras algorithm from this psuedocode:
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
The code I have written is this:
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
It gives me KeyError = 0, I Presume this is to do with line L[v] = L[u] + weight. Other than that I think the code is correct. If anyone spots the issue please let me know, cheers.
Upvotes: 1
Views: 308
Reputation: 3765
In your code I see u = inf or u = L[...]
, yet in original pseudocode u
is a graph vertice, not weight. In other words you confused distances with vertices. Perhaps use strings to name vertices?
Provide example of your graph format. Is G[1] a dictionary with transition keys? list of pairs of a transition with its weight? Looks like in different place it is interpreted differently.
{u,v} or {v,u} == i[0]
is obviously error, you likely meant {u,v} == i[0] or {v,u} == i[0]
Upvotes: 2