Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmo de Dijkstra - Coggle Diagram

- - - - OBS: Caminhos diferentes podem ter arestas em comum.
  - - - Internet - como decidir o caminho de um pacote a ser transmitido na rede
      - Algoritmos de escala de aviões
      - Pathfinding - em jogos
  - - - ...
        
        Encontra menor caminho da fonte ao i-ésimo vértice mais próximo
        
        Em geral, na i-ésima iteração já foram encontrados os caminhos mais curtos dos outros i-1 vértices mais próximos a fonte
        
        Os vértices, fonte e arestas dos menores caminhos formam uma subárvore Ti do grafo
        
        Dentre os vértices à margem de Ti, seleciona o próximo vértice mais próximo da fonte
        
        Para identificar o i-ésimo vértice mais próximo da fonte, é computado, para todo vértice marginal u, a soma da distância do vértice da árvore mais próxima v (= peso da aresta entre u e v) e do comprimento dv (= menor caminho da fonte até v)
        
        Seleciona o vértice que tem a menor soma
        
        Como o peso de todas arestas são não-negativos, o próximo vértice mais próximo da fonte também é encontrado em um dos vértices adjacentes aos vértices de Ti
  - - - Θ(|V|^2)
    - - Θ(|E| x log|V|)