DAA - caminhos mais curtos

Algoritmo de Dijkstra

O algoritmo de Dijkstra resolve o problema de caminhos mais curtos de fonte única em um grafo direcionado ponderado G = (V, E) , onde todas as arestas são não negativas (ou seja, w (u, v) ≥ 0 para cada aresta (u, v ) Є E ).

No algoritmo a seguir, usaremos uma função Extract-Min(), que extrai o nó com a menor chave.

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

Análise

A complexidade deste algoritmo é totalmente dependente da implementação da função Extract-Min. Se a função extract min for implementada usando busca linear, a complexidade deste algoritmo éO(V2 + E).

Neste algoritmo, se usarmos min-heap em que Extract-Min() função funciona para retornar o nó de Q com a menor chave, a complexidade desse algoritmo pode ser reduzida ainda mais.

Exemplo

Vamos considerar o vértice 1 e 9como vértice inicial e de destino, respectivamente. Inicialmente, todos os vértices exceto o vértice inicial são marcados por ∞ e o vértice inicial é marcado por0.

Vértice Inicial Etapa 1 V 1 Etapa 2 V 3 Etapa 3 V 2 Etapa 4 V 4 Etapa 5 V 5 Etapa 6 V 7 Etapa 7 V 8 Etapa 8 V 6
1 0 0 0 0 0 0 0 0 0
2 ∞ 5 4 4 4 4 4 4 4
3 ∞ 2 2 2 2 2 2 2 2
4 ∞ ∞ ∞ 7 7 7 7 7 7
5 ∞ ∞ ∞ 11 9 9 9 9 9
6 ∞ ∞ ∞ ∞ ∞ 17 17 16 16
7 ∞ ∞ 11 11 11 11 11 11 11
8 ∞ ∞ ∞ ∞ ∞ 16 13 13 13
9 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 20

Portanto, a distância mínima do vértice 9 do vértice 1 é 20. E o caminho é

1 → 3 → 7 → 8 → 6 → 9

Este caminho é determinado com base nas informações do predecessor.

Algoritmo Bellman Ford

Este algoritmo resolve o problema do caminho mais curto de fonte única de um gráfico direcionado G = (V, E)em que os pesos das bordas podem ser negativos. Além disso, este algoritmo pode ser aplicado para encontrar o caminho mais curto, caso não exista nenhum ciclo de ponderação negativa.

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

Análise

O primeiro for loop é usado para inicialização, que é executado em O(V)vezes. Nas próximasfor loop é executado |V - 1| passa pelas bordas, o que levaO(E) vezes.

Portanto, o algoritmo Bellman-Ford é executado em O(V, E) Tempo.

Exemplo

O exemplo a seguir mostra como o algoritmo Bellman-Ford funciona passo a passo. Este gráfico tem uma borda negativa, mas não tem nenhum ciclo negativo, portanto, o problema pode ser resolvido usando esta técnica.

No momento da inicialização, todos os vértices exceto a fonte são marcados por by e a fonte é marcada por 0.

Na primeira etapa, todos os vértices acessíveis da fonte são atualizados por custo mínimo. Portanto, vérticesa e h são atualizados.

Na próxima etapa, vértices a, b, f e e são atualizados.

Seguindo a mesma lógica, nesta etapa os vértices b, f, c e g são atualizados.

Aqui, vértices c e d são atualizados.

Portanto, a distância mínima entre o vértice s e vértice d é 20.

Com base nas informações do predecessor, o caminho é s → h → e → g → c → d