Алгоритм Джикстра не работает с кучами в Python - PullRequest
Новая
       17

Алгоритм Джикстра не работает с кучами в Python

0 голосов
/ 08 июля 2019

Я хочу реализовать алгоритм Джикстра, используя кучи для задачи вызова в этом файле в модуле этой страницы -> Тестовые случаи и наборы данных для проектов программирования -> Проблемы программирования 9.8 и10.8. Реализация алгоритма Дейкстры

Я реализовал алгоритм Дикстры с использованием куч и наивного метода.Наивный метод работает для задачи вызова, но тот, который использует кучи, имеет разные и неправильные результаты.

Я создал функцию testcase (), которая возвращает граф networkx с узлами, вершинами и весами задачи.Я передаю этот граф, возвращаемый функцией testcase (), для следующих реализаций алгоритма Джикстра.

Алгоритм Джикстра, использующий простую реализацию: 

%matplotlib inline
import networkx as nx
import heapq
import numpy as np

def undirected_djikstra_naive(DG, source, destination):
    X = [source]
    A = {}
    A[source] = 0
    all_nodes = list(DG.nodes)
    minimum_2nd_overall = float('inf')
    w_overall = float('inf')
    print("Naive:")
    while len(X) != len(all_nodes):
        for edge in list(DG.edges):
            if (edge[0] in X) and (edge[1] not in X):
                edge_tail = edge[0]
                edge_head = edge[1]
            elif (edge[1] in X) and (edge[0] not in X):
                edge_tail = edge[1]
                edge_head = edge[0]
            if ((edge_tail in X) and (edge_head not in X)) :
                dji_greedy = A[edge_tail] + DG.edges[edge_tail, edge_head]['weight'] #djikstra's greedy criterion
                if edge_head not in A:
                    A[edge_head] = dji_greedy
                elif dji_greedy < A[edge_head]:
                    A[edge_head] = dji_greedy
                if dji_greedy < minimum_2nd_overall:
                    minimum_2nd_overall = dji_greedy
                    w_overall = edge_head  
        minimum_2nd_overall = float('inf')
        X.append(w_overall)
    #print("Printing minimum distances from starting vertex {}".format(source))
    B = []
    for node in A:
        if node in destination:
            #print("Vertex {} is at distance {}".format(node, A[node]))
            B.append([node, A[node]])
    B = sorted(B)
    return B

Алгоритм Джикстра, использующий реализацию кучи: 

%matplotlib inline
import networkx as nx
import heapq
import numpy as np

def undirected_djikstra_heap(DG, source, destination):
    #Heap implementation which does the following
    #
    # 1. For vertices in X, find all edges originating from them to all vertices not in X
    # 2. Keep track of minimum value of len(w) + lwv
    # 3. Return w, v and lwv
    X = [source]
    minHeap = []
    heapq.heappush(minHeap, [0, source])
    all_nodes = list(DG.nodes)
    for node in all_nodes:
        DG.nodes[node]['shortest_dist'] = float('inf') 
    print("Heap:")
    while len(minHeap) != 0:
        w = heapq.heappop(minHeap)
        #print(minHeap)
        X.append(w[1])
        DG.nodes[w[1]]['shortest_dist'] = w[0]
        for edge in list(DG.edges):
            if (edge[0] == w[1]) and (edge[1] not in X):
                edge_tail = edge[0]
                edge_head = edge[1]
            elif (edge[1] == w[1]) and (edge[0] not in X):
                edge_tail = edge[1]
                edge_head = edge[0]
            else:
                continue
            if ((edge_tail == w[1]) and (edge_head not in X)) : # node that has just been popped should be the tail
                dji_greedy = w[0] + DG.edges[edge_tail, edge_head]['weight'] #djikstra's greedy criterion
                if len(minHeap) == 0:
                    heapq.heappush(minHeap, [dji_greedy, edge_head])
                    continue
                singlenp = [i[1] for i in minHeap]
                if edge_head not in singlenp:
                    heapq.heappush(minHeap, [dji_greedy, edge_head])
                else:
                    dest_idx = singlenp.index(edge_head)
                    if dji_greedy < minHeap[dest_idx][0]:
                        minHeap[dest_idx] = minHeap[0]
                        heapq.heappop(minHeap)
                        heapq.heappush(minHeap, [dji_greedy, edge_head])
    #print("Printing minimum distances from starting vertex \'{}\'".format(source))
    B = []
    for node in all_nodes:
        if node in destination:
            #print("Vertex {} is at distance {}".format(node, DG.nodes[node]['shortest_dist']))
            B.append([node, DG.nodes[node]['shortest_dist']])
    B = sorted(B)
    return B

Вызов и утверждение алгоритма: 

challenge_graph_g = testcase()
start_vert = 1
dest_verts = challenge_graph_g.nodes
heap_dji = undirected_djikstra_heap(challenge_graph_g, start_vert, dest_verts)
naive_dji = undirected_djikstra_naive(challenge_graph_g, start_vert , dest_verts)

for a in range(len(dest_verts)):
    assert heap_dji[a][1] == naive_dji[a][1], "Dist Mismatch at Vertex {} dist heap {}, Vertex {} dist naive {}".format(heap_dji[a][0], heap_dji[a][1], naive_dji[a][0], naive_dji[a][1])

Я получаю ошибку подтверждения для вывода вершины 2 следующим образом:

AssertionError: Dist Mismatch в Vertex 2, куча dist 3428, Vertex2 dist naive 2971

Я не понимаю, где и для каких случаев моя куча не работает.Пожалуйста, помогите.

Решение:

Heapify итерируемой после операции вставки / удаления вручную в heapq.Выполнено heapq.heapify (minHeap) после minHeap [dest_idx] = minHeap [0] ручное обновление кучи.

Модифицированный код:

Алгоритм Джикстра с использованием реализации кучи: 

%matplotlib inline
import networkx as nx
import heapq
import numpy as np

def undirected_djikstra_heap(DG, source, destination):
    #Heap implementation which does the following
    #
    # 1. For vertices in X, find all edges originating from them to all vertices not in X
    # 2. Keep track of minimum value of len(w) + lwv
    # 3. Return w, v and lwv
    X = [source]
    minHeap = []
    heapq.heappush(minHeap, [0, source])
    all_nodes = list(DG.nodes)
    for node in all_nodes:
        DG.nodes[node]['shortest_dist'] = float('inf') 
    print("Heap:")
    while len(minHeap) != 0:
        w = heapq.heappop(minHeap)
        #print(minHeap)
        X.append(w[1])
        DG.nodes[w[1]]['shortest_dist'] = w[0]
        for edge in list(DG.edges):
            if (edge[0] == w[1]) and (edge[1] not in X):
                edge_tail = edge[0]
                edge_head = edge[1]
            elif (edge[1] == w[1]) and (edge[0] not in X):
                edge_tail = edge[1]
                edge_head = edge[0]
            else:
                continue
            if ((edge_tail == w[1]) and (edge_head not in X)) : # node that has just been popped should be the tail
                dji_greedy = w[0] + DG.edges[edge_tail, edge_head]['weight'] #djikstra's greedy criterion
                if len(minHeap) == 0:
                    heapq.heappush(minHeap, [dji_greedy, edge_head])
                    continue
                singlenp = [i[1] for i in minHeap]
                if edge_head not in singlenp:
                    heapq.heappush(minHeap, [dji_greedy, edge_head])
                else:
                    dest_idx = singlenp.index(edge_head)
                    if dji_greedy < minHeap[dest_idx][0]:
                        minHeap[dest_idx] = minHeap[0]
                        heapq.heapify(minHeap)    # Added this single line
                        heapq.heappop(minHeap)
                        heapq.heappush(minHeap, [dji_greedy, edge_head])
    #print("Printing minimum distances from starting vertex \'{}\'".format(source))
    B = []
    for node in all_nodes:
        if node in destination:
            #print("Vertex {} is at distance {}".format(node, DG.nodes[node]['shortest_dist']))
            B.append([node, DG.nodes[node]['shortest_dist']])
    B = sorted(B)
    return B

С этим измененнымкод, наивная реализация и реализация кучи алгоритма Джикстры дают одинаковый результат в наборе данных вызова.

...