Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Sendo \emph{V} o número de vértices a analisar e \emph{E} o número de arestas, o algoritmo percorre primeiramente toda a lista de vértices para inicializar valores. Esta operação tem complexidade \emph{V}.Acrescenta-se, com complexidade $O(1)$, a fonte à fila de prioridade. De seguida percorre-se a fila de prioridade, recorrendo a função de extração do menor elemento da fila. Num heap de fibonacci esta operação correm em tempo $log(V)$. Obtem-se assim para este ciclo uma complxidade $Vlog(V)$. Dentro deste ciclo todas as arestas do grafo acabam por ser analisadas, sendo, quando encontrada uma aresta que constitua um caminho mais favorável, chamada a função DecreaseKey do fibanacci heap, que corre em tempo constante. Obtem-se assim uma complexidade linear $E$.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement