Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorítimo de Dijkstra - Coggle Diagram
Algorítimo de Dijkstra
Encontrar o menor caminho partindo de um vértice (source) até outro vértice em um grafo com pesos não negativos
Primeiro encontrar o menor caminho do vértice source até um vértice diferente com menor peso
Gerando uma sub-árvore T
De forma que o próximo vértice a ser inserido em T será o vértice adjacente mais próximo de T
Vértices adjacentes de uma árvore são chamados de fringe vértices
Para identificar o próximo vértice mais próximo é feito a soma do da distância para o vértice mais próximo da árvore
2 rótulos em cada vértice
Um numérico d indica o comprimento do caminho mais curto da source até este vértice encontrado pelo algoritmo até agora
Outro é o pai do vértice da árvore que está sendo construída
De forma que encontrar o próximo vértice U* se torna encontrar o menor d
Ao encontraro próximo vértice U* a ser inserido na árvore
Mover U* para os vértices na árvore
Atualizar os rótulos dos outros fringe vértices
1 more item...
Listas com prioridade
Matriz
Θ(|V²|)
Lista
O(|E| log|V| )
V=vértices do grafo
E=arestas do grafo