Временная сложность дейкстры с использованием минимальной кучи Фибоначчи - PullRequest
Новая
       13

Временная сложность дейкстры с использованием минимальной кучи Фибоначчи

3 голосов
/ 14 мая 2019

Я пытался оптимизировать свой алгоритм Дейкстры, используя минимальную кучу Фибоначчи, которая в соответствии с этим 1 [статья] должна принимать сложность $ O (M + N log (N) ) $ где:

  • M - количество ребер
  • N - количество вершин

Я вычислил общую сложность, но я не уверен, что она правильная, и я хотел бы получить некоторые предложения:

Во-первых, у нас есть «объявления и присваивания», которых я постараюсь избегать, поскольку все они являются постоянными элементарными операциями, которые принимают $ O (1) $ и не имеют вклада в мою сложность как n $ \ to $. $ \ infty $.

Первый цикл for, который принимает сложность $ O (N) $.

Метод headpop, который принимает $ O (log (N)) $, предполагая, что мы ищем узел с наименьшим весом в двоичной куче.

Здесь я не уверен. Таким образом, мы берем узел с небольшим весом из источника и затем обновляем метки соседей, что означает, что мы идем в список смежности (в данном случае словарь) и проверяем все возможные ребра в наборе $ \ delta ^ + (v) $, то есть все узлы, идущие от v к другой вершине u из множества $ \ S $, содержащего уже посещенные узлы. Таким образом, общая сложность $ O (n-1) $ для полных графиков.

Имея все это в виду, я получил: $ O (N \ cdot (log (N) + M)) $ $ \ эквивалента $ $ O (N \ cdot (log (N) + N - 1)) $ $ \ эквивалента $ O (N \ cdot log (N) + N ^ 2) $ $ \ эквивалента $ $ O (N ^ 2) $ для больших значений N.

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

def dijkstra2(successors, s):

    S = []; S.append(s)
    n = len(successors)
    L = dict(); L[s] = 0
    P = dict(); P[s] = '-'

    # Iterate through the V/{s}-nodes and set L[j] to infinity and P[j] to s.
    for o in range(0, n):
        if o != s:
            L[o] = numpy.inf
            P[o] = s

    # Visited vector.
    visited = [False] * n;

    # Heapq
    queue = [(0, s)];


    while queue:
        par_len, v = heappop(queue);
        # v is unvisited
        if visited[v] is False:
            visited[v] = True
            for w, edge_len in successors[v].items():
                # Check if the child is unvisited and compute the distance.
                if visited[w] is False and edge_len + par_len < L[w] :
                    heappush(queue, (edge_len + par_len, w))
                    L[w] = edge_len + par_len
                    P[w] = v

    return L, P

1 Ответ

1 голос
/ 14 мая 2019

Алгоритм Дейкстры: 

O(|E| |decrease-key(Q)| + |V| |extract-min(Q)|)

Куча Фибоначчи: 

O(|E| + |V| log |V|)

двоичная куча: 

O((|E| + |V|) log |V|)

E: 

|E| = O(|V|^2)

Q это: Очереди с минимальным приоритетом упорядочиваются по собственной текущей оценке расстояния.

Инициализация кучи: 

from heapq import *
from random import randint

f = FibonacciHeap()
h = []
n = 100
for i in xrange(0, n):
    r = randint(1, 1000)
    f.insert(r)
    heappush(h, r)

Код для времени печати: 

import time
# test fib heap running time 
start_time = time.time()
while f.total_nodes > 0:
    m = f.extract_min()
print "%s seconds run time for fib heap" % (time.time() - start_time)

# test heapq running time 
start_time = time.time()
while h:
    m = heappop(h)
print "%s seconds run time for heapq" % (time.time() - start_time)
...