Алгоритм кратчайших путей Дейкстры с частично упорядоченным деревом в качестве очереди с приоритетами - PullRequest
Новая
       54

Алгоритм кратчайших путей Дейкстры с частично упорядоченным деревом в качестве очереди с приоритетами

0 голосов
/ 15 марта 2020

Я пытался преобразовать код C из следующего источника, чтобы реализовать Дейкстру с частично упорядоченным деревом в качестве очереди приоритетов и связанными списками смежности в качестве представления графа. 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

**

Может ли кто-нибудь помочь мне чтобы выяснить, почему я получаю неправильные результаты? Спасибо!

1 Ответ

0 голосов
/ 15 марта 2020

Ваши индексы неверны в строке, в которой указана ошибка, и в нескольких других строках 

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