Advertisement
Guest User

Untitled

a guest
Apr 25th, 2015
214
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.77 KB | None | 0 0
  1. 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