Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de caminhos mínimos - Coggle Diagram
Algoritmos de caminhos mínimos
Dijkstra
Requisitos
Grafo com pesos não negativos
Utiliza fila de prioridade (min-heap)
Tem como objetivo encontrar caminho mínimo de um vértice origem para todos os demais (single-source)
Complexidade
: O((V + E) log V)
Funcionamento
:
Escolhe vértice com menor distância ainda não visitado
Relaxa arestas (atualiza distâncias)
Repete até todos os vértices estarem processados
Floyd-Warshall
Tem como objetivo formar caminhos mínimos entre todos os pares de vértices (all-pairs)
Complexidade:
O(V³)
Estratégia
Permite pesos negativos (sem ciclos negativos)
Programação dinâmica
Funcionamento
Usa matriz D[i][j] com distâncias
Iterações com vértices intermediários (k): D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Bellman-Ford
Tem como objetivo encontrar caminhos mínimos a partir de um único vértice (single-source)
Complexidade
: O(V × E)
Vantagens
Suporta pesos negativos e ciclos negativos
Funcionamento
Repete V−1 vezes: percorre todas as arestas e relaxa
-Verifica na Vª iteração se ainda houve melhoria → ciclo negativo