Можно ли изменить этот код, чтобы очередь приоритетов уменьшала свой ключ за время O (logn)?

Question

Попытка написать дейкстры на питоне.Как мне реализовать операцию уменьшения ключа в O (logn), когда я не могу изменить свои кортежи?

Я пишу фрагмент кода, чтобы решить dijkstras в списке смежности и требовать реализации очереди приоритетов.В настоящее время я передаю кортеж (priority, value) в pq, поэтому heapify обрабатывает push и pop для меня.Тем не менее, я не могу изменить кортежи, поэтому я не могу эффективно уменьшить приоритет любого элемента и вынужден извлекать все элементы до тех пор, пока не будет найден нужный элемент, а затем записать все элементы в pq, что усложняет время O (V ^2).Есть ли способ изменить этот код, чтобы операция lowerKey работала за O (logn)?Желательно, чтобы не было занятий.Я не могу использовать списки вместо кортежей;в противном случае он не будет складываться в кучу

def decrease_key(pq, v, val):
    li = []
    u = heapq.heappop(pq)

    while u[1] is not v:
        li.append(u)
        u = heapq.heappop(pq)

    for l in li:
        heapq.heappush(pq, l)

    heapq.heappush(pq, (val, v))


def dijkstra(G, src, dist, V):

    for v in range(V):
        dist[v] = float('inf')
    dist[src] = 0

    pq = []

    for k, v in dist.items():
        pq.append((v, k))

    while pq:
        u = heapq.heappop(pq)[1]
        for v, w in G[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                decrease_key(pq, v, dist[v])

O (n ^ 2) против требуемого O (nlogn)

Answer 1

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

import heapq

def dijkstra(graph, src):
    # Read all graph nodes
    nodes = list(graph.keys())

    # Initialize all distances to infinity and build a queue of unvisted nodes
    dist = {}
    pq = []
    for node in nodes:
        dist[node] = float('inf')
    dist[src] = 0
    heapq.heappush(pq, (0, src))

    # While shorter distances to nodes, recalculate neighbor distances
    while pq:
        src_dist, unvisited_node = heapq.heappop(pq)

        # Recalculate total distance for each neighbor
        unvisted_neighbors = graph.get(unvisited_node, [])
        for n_node, n_dist in unvisted_neighbors:
            test_dist = src_dist + n_dist

            # If test distance is shorted, update and enqueue
            if test_dist < dist[n_node]:
                dist[n_node] = test_dist
                heapq.heappush(pq, (test_dist, n_node))

    return dist

test_graph = {
    'a': (('b',  7), ('c',  9), ('f', 14)),
    'b': (('a',  7), ('d', 15), ('c', 10)),
    'c': (('a',  9), ('b', 10), ('d', 11), ('f',  2)),
    'd': (('b', 15), ('c', 11), ('e',  6)),
    'e': (('d',  6), ('f',  9)),
    'f': (('c',  2), ('e',  9))
}
'''Lazy graph structure.

key: source node name
value: adjacent node name and distance pairs

https://www.bogotobogo.com/python/images/Graph/graph_diagram.png
'''
src_node = 'e'
d = dijkstra(test_graph, src_node)
for k, v in d.items():
    print(f'{src_node}->{k}: {v}')

Answer 2

Как указывает @DavidEisenstat в комментариях, вам не нужно уменьшать_ключ, если вы просто добавляете несколько записей в кучу.

Вам также необходимо отслеживать, какие узлы вы выдвинули из очереди с приоритетами,таким образом, вы можете обработать узел только в первый раз.(В противном случае сложность в наихудшем случае возрастает)

И, наконец, было бы хорошо, если вы избегаете помещать эти бесконечные затраты в кучу, и если вы толкаете новый узел только тогда, когда вы фактически снижаете стоимость.Все вместе, примерно так:

def dijkstra(G, src, dist, V):

    for v in range(V):
        dist[v] = float('inf')
    dist[src] = 0

    pq = [(0,src)]
    seen = [False]*V

    while pq:
        u = heapq.heappop(pq)[1]
        if seen[u]:
            continue
        seen[u] = True
        for v, w in G[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush( pq, (dist[v],v) )