以偏序树为优先队列的 Dijkstra 最短路径算法

Question

我试图将来自以下源的 C 代码转换为使用部分有序树作为优先级队列并将链接的邻接列表作为图形表示的 Dijkstra 实现。 http://infolab.stanford.edu/~ullman/fcsccode/fig9.44-47.txt

我做了以下操作，但它没有按预期工作并且还抛出一个 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)

它产生以下输出：

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

**预期输出：

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

**

有人可以帮我找出为什么我得到错误的结果吗？谢谢！

Answer 1

您的索引在错误所在的行和其他几行上不正确

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))

您还需要修改这两行以获得正确的结果：

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

输出：

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

以偏序树为优先队列的 Dijkstra 最短路径算法

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

python

dijkstra

priority-queue