Dijkstra’s Algorithm issue and key error in python

Question

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.

KeyError Traceback (most recent call last) <ipython-input-24-8f2b0430a74c> in <module>() ----> 1 dijkstras(G,start,stop) <ipython-input-22-2dfe8c78e45d> in dijkstras(G, start, stop) 26 else: 27 weight = inf ---> 28 if L[u] + weight < L[v]: 29 L[v] = L[u] + weight 30 return stop KeyError: 0 — corrigan_sam
– corrigan_sam, Commented May 2, 2018 at 16:18
what is your graph format, key should not be mutable. Provide example of the graph. In python {u,v} denotes set not pair. Pair would be (u, v) — Serge
– Serge, Commented May 2, 2018 at 16:18

Serge · Accepted Answer · 2018-05-03 02:24:55Z

2

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]

edited May 3, 2018 at 2:24

answered May 2, 2018 at 16:22

Serge

3,8453 gold badges20 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Dijkstra’s Algorithm issue and key error in python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related