Dijkstra's shortest paths algorithm with a partially ordered tree as a priority queue

Question

I was trying to convert a C code from the following source to implement Dijkstra with a partially ordered tree as a priority queue and linked adjacency lists as the representation of the graph. http://infolab.stanford.edu/~ullman/fcsccode/fig9.44-47.txt

I did the following, but it doesn't work as expected and also throws an Indexerror.

class Node():
    def __init__(self):
        self.name = None
        self.label = None
        self.next = None

class GraphElement():
    def __init__(self):
        self.dist = None
        self.successors = None
        self.toPot = None

MAX = 6
INFTY = 100

def swap(a, b, G, P):
    temp = Node()
    temp = P[b]
    P[b] = P[a]
    P[a] = temp

    G[P[a]].toPot = a
    G[P[b]].toPot = b


def priority(a, G, P):
    return G[P[a]].dist

def bubbleUp(a, G, P):
    if (a > 1):
        if priority(a, G, P) < priority(a//2, G, P):
            swap(a, a//2, G, P)
            bubbleUp(a//2, G, P)

def bubbleDown(a, G, P, last):
    child = 2*a
    if (child < last):
        if priority(child+1, G, P) < priority(child, G, P):
            child += 1

def initialize(G, P, pLast):
    for i in range(0, MAX):
        G[i].dist = INFTY
        G[i].toPot = i+1
        P[i+1] = i

    # P[0] = 0
    G[0].dist = 0
    pLast = MAX

def Dijkstra(G, P, pLast):
    u = Node()
    v = Node()
    initialize(G, P, pLast)

    count = 1
    while(pLast >= 1):
        v = P[1]
        swap(1, pLast, G, P)
        pLast -= 1
        bubbleDown(1, G, P, pLast)
        ps = G[v].successors


        while (ps != None):
            u = ps.name
            print(str(count) + " to " + str(u) + ":")
            if G[u].dist > G[v].dist + ps.label:

                G[u].dist = G[v].dist + ps.label
                bubbleUp(G[u].toPot, G, P)
            print(str(G[u].dist))

            ps = ps.next


if __name__ == '__main__':

    A12 = Node()
    A12.name = 2
    A12.label = 4

    A13 = Node()
    A13.name = 3
    A13.label = 1

    A14 = Node()
    A14.name = 4
    A14.label = 5

    A15 = Node()
    A15.name = 5
    A15.label = 8

    A16 = Node()
    A16.name = 6
    A16.label = 10

    A32 = Node()
    A32.name = 2
    A32.label = 2

    A45 = Node()
    A45.name = 5
    A45.label = 2

    A56 = Node()
    A56.name = 6
    A56.label = 1

    graph = []
    for i in range(MAX):
        graph.append(GraphElement())

    graph[0].successors = A12
    A12.next = A13
    A13.next = A14
    A14.next = A15
    A15.next = A16
    A16.next = None

    graph[1].successors = None

    graph[2].successors = A32
    A32.next = None

    graph[3].successors = A45
    A45.next = None

    graph[4].successors = A56
    A56.next = None

    graph[5].successors = None

    potNodes = []
    for i in range(MAX+1):
        potNodes.append(Node())

    PotNode = []
    for i in range(MAX):
        PotNode.append(Node())

    print("The shortest path from node: ")
    Dijkstra(graph, potNodes, MAX)

It produces the following output:

1 to 2:
4
1 to 3:
1
1 to 4:
5
1 to 5:
8
1 to 6:
    Dijkstra(graph, potNodes, MAX)
      if G[u].dist > G[v].dist + ps.label:
IndexError: list index out of range

Process finished with exit code 1

**Expected output:

1 to 2:
3
1 to 3:
1
1 to 4:
5
1 to 5:
7
1 to 6:
8

**

Can someone help me to find out why I'm getting the wrong results? Thank you!

Answer 1

Your indexes are incorrect on the line the error is on and a few other lines

print(str(count) + " to " + str(u) + ":")
if G[u-1].dist > G[v].dist + ps.label:

    G[u-1].dist = G[v].dist + ps.label
    bubbleUp(G[u-1].toPot, G, P)
print(str(G[u-1].dist))

You also need to amend these two lines to get the correct result:

G[P[a]].toPot = a-1
G[P[b]].toPot = b-1

Output:

The shortest path from node: 
1 to 2:
4
1 to 3:
1
1 to 4:
5
1 to 5:
8
1 to 6:
10
1 to 2:
3
1 to 5:
7
1 to 6:
8