Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de caminhos mínimos - Coggle Diagram
Algoritmos de caminhos mínimos
Floyd (All-Pairs)
Problema
distâncias mínimas entre todos os pares de vértices
Ideia central
matriz D^(k): menor caminho entre i e j usando intermediários ≤ k
fórmula: D[i,j] = min(D[i,j], D[i,k] + D[k,j])
Complexidade
Tempo: O(n³)
Espaço: O(n²)
Dijkstra (Single-Source)
Problema
menor caminho de fonte s a todos os vértices (pesos ≥0)
Ideia central
construir árvore de caminhos mínimos
usa rótulo d_v (distância) e p_v (pai)
Passos principais
inicializa d_v = ∞ (todos), d_s = 0; insere todos em fila prioridade
enquanto fila não vazia
retira u* com menor d
para cada vizinho u de u*
se d_u
+ w(u
,u) < d_u
atualiza d_u e p_u; decrease-key
Complexidade
Matriz + fila simples: O(|V|²)
Lista adj. + min‑heap: O(|E| log |V|)