Edit page

Caminhos Mais Curtos

Problema

O professor Patrick quer descobrir o caminho mais curto de Phoenix a Indianapolis. Dado um mapa dos Estados Unidos (onde a distância entre cada par de interseções adjacentes está marcada), como pode ele determinar o caminho mais curto?

O livro que acompanha a cadeira introduz assim o tema dos caminhos mais curtos em grafos. Como podemos, então, ajudar o professor Patrick (e de forma eficiente)?

Num problema de caminhos mais curtos, é-nos dado um grafo dirigido pesado, G=(V,E)G = (V, E), com uma função de pesos ww que mapeia cada aresta de EE a um peso numérico. O peso ww de um dado caminho pp corresponderá, então, à soma dos pesos de todas as arestas que compõem o caminho, tal que:

w(p)=i=1kw(vi1,vi)w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i)

O peso do caminho mais curto, dado por δ(u,v)\delta(u, v), é definido tal que:

δ(u,v)={min{w(p):upv}se existe caminho de u para vcaso contraˊrio\delta(u, v) = \begin{cases} \min {\{w(p): u \to_{p} v\}} & \text{se existe caminho de u para v}\\ \infty & \text{caso contrário} \end{cases}

O caminho mais curto de uu para vv é, portanto, qualquer caminho pp tal que δ(u,v)=w(p)\delta(u, v) = w(p).

Podemos, claro, notar que a BFS corresponde a um algoritmo deste género, que funciona para grafos não-pesados/com pesos uniformes.

Arcos com peso negativo

Podemos, ao resolver problemas de caminho mais curto, acabar por nos deparar com arcos com peso negativo. Caso um grafo GG não contenha ciclos de peso negativo atingíveis a partir da fonte, temos que o peso do caminho mais curto entre a fonte e qualquer outro vértice atingível está bem definido (é sempre o mesmo, portanto), pelo que a existência de arcos de peso negativo não influencia o determinismo da solução. Caso contenha pelo menos um ciclo de peso negativo, não o podemos afirmar - tratando-se de um ciclo, podemos percorrê-lo infinitamente. Sendo o seu peso negativo, o "caminho mais curto" será tão mais curto (isto é, menos pesado) quantas mais vezes o percorrermos, chegando, no limite, a -\infty. Abaixo podemos encontrar um exemplo do mesmo, onde o caminho de ss, fonte, ao vértice zz passa por um ciclo negativo:

Caminho mais Curto - Ciclo Negativo

O algoritmo de Dijkstra, abordado mais à frente, assume que o grafo argumento não tem ciclos negativos. Pelo contrário, o algoritmo de Bellman-Ford permite que tal ocorra: retorna uma resposta caso o grafo não contenha ciclos de peso negativo, reportando a existência dos mesmos, sem devolver uma resposta, caso contrário.

Caminhos mais Curtos com Fonte Única

Esta secção irá abordar a identificação do caminho mais curto partindo de um vértice-fonte sVs \in V a qualquer vértice vVv \in V. O algoritmo em questão permitirá resolver outros problemas, tais como:

  • Caminhos mais Curtos com Destino Único (corresponde a inverter a direção de cada aresta e aplicar o algoritmo normal de caminhos mais curtos de fonte única).

  • Caminhos mais Curtos entre Par Único (corresponde a identificar o caminho mais curto entre dois vértices).

  • Caminhos mais Curtos entre todos os Pares (corresponde a uma generalização do último, em que encontramos o caminho mais curtos entre cada par de vértices do Grafo).

Serão abordados três algoritmos principais, com use-cases diferentes consoante o grafo em mãos:

  • Algoritmo de Dijkstra, que não permite arcos com peso negativo.

  • Algoritmo de Bellman-Ford, que permite arcos com peso negativo e identifica ciclos negativos.

  • Caminhos mais Curtos em DAGs, que só permite grafos acíclicos.

Representação e Propriedades de Caminhos mais Curtos

Tenhamos G=(V,E)G = (V, E), um grafo dirigido e pesado, com função de pesos w:ERw: E \to \R. Assumimos que o mesmo não contém ciclos com peso negativo atingíveis a partir da fonte. Assim sendo, podemos afirmar que a sua árvore de caminhos mais curtos é um sub-grafo de GG dirigido, G=(V,E),VVEEG' = (V', E'), V' \subseteq V \wedge E' \subseteq E, tal que:

  • VV' corresponde ao conjunto de vértices atingíveis a partir de SS em GG.

  • GG' forma uma árvore com raiz em ss (a fonte).

  • vV\forall_{v \in V'}, o único caminho de ss até vv em GG' é o caminho mais curto de ss até vv em GG.

Podemos, claro, notar que os caminhos mais curtos não são necessariamente únicos, e, por consequência, nem as árvores de caminhos mais curtos o são. Abaixo temos um exemplo de duas árvores de caminhos mais curtos diferentes:

Caminhos Mais Curtos - Árvores diferentes

Temos ainda que todo o sub-caminho de um caminho mais curto é também um caminho mais curto. Tenhamos, por exemplo, o caminho p=(s,v1,v2,...,vk)p = (s, v_1, v_2, ..., v_k). Seja, ainda, pijp_{ij} um sub-caminho de pp, de viv_i até vjv_j. Podemos afirmar que pijp_{ij} é um caminho mais curto de viv_i até vjv_j em GG, dado que, caso tal não acontecesse, poderíamos construir um caminho mais curto de ss a vkv_k, contradizendo a premissa de pp ser um caminho mais curto.

Podemos, decompondo um caminho, voltar a definir uma recorrência para o seu peso. Tendo p=(s,...,u,v)p = (s, ..., u, v) e psup_{su} um caminho tal que pp pode ser decomposto em psu=(s,...,u)p_{su} = (s, ..., u) e (u,v)(u, v), então δ(s,v)=δ(s,u)+w(u,v)\delta(s, v) = \delta(s, u) + w(u, v):

  • psup_{su} é um caminho mais curto de ss a uu.

  • δ(s,v)=w(p)=w(psu)+w(u,v)=δ(s,u)+w(u,v)\delta(s, v) = w(p) = w(p_{su}) + w(u, v) = \delta(s, u) + w(u, v).

Podemos, por fim, afirmar que δ(s,v)δ(s,u)+w(u,v)\delta(s, v) \leq \delta(s, u) + w(u, v). Escrevemos \leq em vez de == porque pode haver um sub-caminho mais barato de ss a vv que não inclua necessariamente o arco (u,v)(u, v), como no exemplo abaixo:

Subcaminho mais Barato

Relaxação

Os algoritmos abordados mais abaixo irão recorrer à operação de relaxação. É mantido um vector, dd, com V|V| elementos, onde para cada vértice vVv \in V de G=(V,E)G = (V, E), d[v]d[v] denota a estimativa atual do caminho mais curto de ss até vv. Corresponderá a um majorante do peso do mesmo - isto é, se já sabemos que a melhor estimativa que temos é aquela, nunca iremos atualizar a mesma caso se trate de um custo mais caro. O algoritmo começa por inicializar todas as estimativas a ++\infty, bem como todos os pais de todos os vértices a Nil:

InitializeSingleSource(G, s) // ocorre em Theta(|V|) tempo
  for each v in V[G] do
    d[v] := +infinity
    pi[v] := Nil
  d[s] := 0 // temos, claro, que o custo de s a s é 0

Relaxar uma aresta (u,v)(u, v) consiste em verificar se podemos imediatamente melhorar a nossa estimativa atual do custo de ss a vv passando pela aresta (u,v)(u, v) - caso possamos, atualizamos tanto a nossa estimativa como o pai de vv:

Relax(G, u, v, w) // ocorre em Theta(1) tempo
  if d[v] > d[u] + w(u, v) then
    d[v] := d[u] + w(u, v)
    pi[v] := u

Abaixo encontramos exemplos de relaxação de arestas:

Caminhos mais Curtos - Relaxação de Arestas

No caso (a)(a), tínhamos que d[u]d[u] tinha estimativa atual 55 e que d[v]d[v] tinha estimativa atual 99. Assim, como a aresta que estávamos a ver tinha peso 2, atualizamos a estimativa de vv para 77 e o pai de vv para uu, já que deste modo temos uma estimativa mais barata em vv. Por outro lado, em (b)(b), d[u]d[u] tinha estimativa atual 55 e d[v]d[v] tinha estimativa atual 66. Com uma aresta de custo 2, não faz sentido atualizar agora a estimativa de vv para 77, pelo que nada acontece.

Propriedades da Relaxação

  • d[v]δ(s,v),vVd[v] \geq \delta(s, v), \forall_{v \in V} - a estimativa é atualizada ao longo do algoritmo, não podendo, contudo, ser menor que o custo final, seria uma contradição. Mais ainda, quando d[v]=δ(s,v)d[v] = \delta(s, v), d[v]d[v] nunca se voltará a alterar.

  • Caso não haja um caminho de ss a vv, d[v]d[v] nunca será atualizado, mantendo-se portanto sempre a ++\infty.

  • Seja p=(s,...,u,v)p = (s, ..., u, v) um caminho mais curto de ss a vv, passando por uu. Se tivermos d[u]=δ(s,u)d[u] = \delta(s, u) num qualquer momento anterior à relaxação de (u,v)(u, v), então d[v]=δ(s,v)d[v] = \delta(s, v).

  • De modo semelhante à propriedade anterior, tendo p=(s,t,...,u,v)p = (s, t, ..., u, v) um caminho mais curto de ss a vv, se relaxarmos as arestas de pp pela ordem (s,t)(s, t), ..., (u,v)(u, v), então d[v]=δ(s,v)d[v] = \delta(s, v). A propriedade mantém-se com quaisquer outras relaxações que se possam fazer posteriormente, dado que estas nunca poderão ter influência - já temos o custo mais baixo, nunca poderá ser mais baixo que isso.

Algoritmo de Dijkstra

O algoritmo de Dijkstra resolve o problema do caminho mais curto de fonte única para um grafo, G=(V,E)G=(V, E), pesado (função de pesos ww) e dirigido, sem arcos negativos. Mantém um conjunto, SS, de vértices cujo respetivo δ\delta já foi calculado.

Trata-se de um algoritmo greedy, cuja escolha greedy corresponde a selecionar sempre o vértice em uVSu \in V - S com menor estimativa de peso mais curto. uu é adicionado a SS e todas as arestas que originam de uu são relaxadas.

O algoritmo tem complexidade temporal no pior caso melhor que a do algoritmo de Bellman-Ford, abordado mais abaixo.

É utilizada uma min priority queue, QQ, para ordenar os vértices de acordo com a sua estimativa de peso mais curto.

Dijkstra(G, w, s)
  InitializeSingleSource(G, s) // ocorre em Theta(V) tempo
  let S := new array
  let Q := new queue(V)
  while Q is not empty do // ocorre Theta(V) vezes
    let u := extractMin(Q) // V vezes * O(logV) durante o algoritmo
    S.add(u)
    for each v in Adj[u] do // Theta(E) vezes durante o algoritmo
      Relax(G, u, v, w(u, v))

A complexidade temporal total do algoritmo é, portanto, Θ((V+E)logV)\Theta((V + E) \cdot \log{V}). Temos ElogVE \cdot \log{V}, não apenas EE, já que por cada operação de relaxação, com a estimativa a ser atualizada, também temos de atualizar o vértice na queue - até logV\log V por vértice. Esta operação está implícita no pseudocódigo.

Exemplo - Aplicação do Algoritmo

Tenhamos o grafo abaixo:

Caminhos mais Curtos - Dijkstra - Grafo, Exemplo 1

Temos, claro, que todos os vértices começam com estimativa ++\infty, exceto ss, com estimativa 00.

O primeiro passo consiste em extrair ss de QQ, adicionando-o a SS, e passar por todas as suas adjacências, procurando relaxá-las. Neste caso, como tanto uu como xx têm estimativa atual ++\infty, são ambos necessariamente atualizados, para 1010 e 55, respetivamente. Como a estimativa de ambos é atualizada, também o respetivo pai é - ss fica pai de ambos. Fica ainda subentendido que, com a atualização das estimativas de cada vértice, a prioridade em QQ de cada um deles é também alterada.

Caminhos mais Curtos - Dijkstra - Passo 2, Exemplo 1

De seguida, xx é extraído de QQ (sendo uma min priority queue e tendo o custo mínimo dentro dos vértices de QQ, a escolha é natural) e adicionado a SS. Tem três arestas que dele originam. vv e yy são atualizados normalmente, já que a sua estimativa é atualmente ++\infty (ficando, respetivamente, com pesos 1414 e 77). uu é também atualizado, desta feita porque o seu peso atual, 1010, é maior que a estimativa agora proposta, 5+3=85 + 3 = 8. O pai é também atualizado (agora xx).

Caminhos mais Curtos - Dijkstra - Passo 3, Exemplo 1

Com estimativa menor atual associada, yy é o escolhido para ser extraído de QQ. Tem apenas um arco que dele origina, para vv, e a estimativa 7+6=137 + 6 = 13 é menor que o seu custo atual, pelo que é atualizado.

Caminhos mais Curtos - Dijkstra - Passo 4, Exemplo 1

É, agora, extraído uu, que tal como yy tem apenas um arco que dele sai, para vv. A sua estimativa é de 8+1=98 + 1 = 9, pelo que a estimativa de vv é atualizada.

Caminhos mais Curtos - Dijkstra - Passo 5, Exemplo 1

Por fim, vv é extraído, não havendo qualquer atualização feita. O grafo resultante fica então assim (as estimativas de cada vértice estão indicadas):

Caminhos mais Curtos - Dijkstra - Passo 6, Exemplo 1

Podemos, no fim, afirmar que o caminho mais curto que se pode fazer entre todos os vértices (com fonte em ss) tem este aspeto:

Caminhos mais Curtos - Dijkstra - Caminho Final

Prova do Invariante do Algoritmo de Dijkstra

Temos, como invariante do algoritmo de Dijkstra, que d[u]=δ(s,u)d[u] = \delta(s, u) quando uu é adicionado a SS, e que esta igualdade é sempre verdade até ao fim do algoritmo. Procuremos prová-lo (recorrendo ao absurdo):

Vamos então assumir que existe um qualquer vértice uu tal que d[u]=δ(s,u)d[u] = \delta(s, u) não é verdade - isto é, que aquando da inserção de uu em ss, a sua estimativa atual de custo não é a menor possível. Temos, claro, que esse vértice uu nunca poderá ser ss (pois ss é o vértice inicial, e o seu custo é invariavelmente zero, dado que estamos a trabalhar apenas com arestas não negativas). Além disso, no momento em que uu é adicionado a SS, SS não está vazio, visto que se sus \neq u e ss é o primeiro elemento a ser adicionado a SS, então este não se pode encontrar vazio aquando da inserção de uu. Por fim, claro, existe necessariamente um qualquer caminho mais curto de ss a uu, caso contrário teríamos que d[u]=δ(s,u)=+d[u] = \delta(s, u) = +\infty.

Vamos, então, supor que uu é o primeiro vértice tal que d[u]δ(s,u)d[u] \neq \delta(s, u) aquando da sua inserção em SS. Além disso, tenhamos que p=(s,...,x,y,...,u)p = (s, ..., x, y, ..., u) é o caminho mais curto de ss a uu. Para d[u]δ(s,u)d[u] \neq \delta(s, u), tem que existir um vértice de pp que ainda não tenha sido inserido em SS, caso contrário teríamos obrigatoriamente d[u]=δ(s,u)d[u] = \delta(s, u), já que o caminho mais curto teria sido completamente explorado, não havendo margem para dúvida.

Consideremos, então, o arco (x,y)(x, y) - um arco que liga dois vértices de pp, com xSySx \in S \wedge y \notin S. Como admitimos anteriormente que uu é o primeiro vértice em que d[u]δ(s,u)d[u] \neq \delta(s, u), temos que d[x]=δ(s,x)d[x] = \delta(s, x). Além disso, temos que d[y]=δ(s,y)d[y] = \delta(s, y), já que (x,y)(x, y) foi relaxado assim que xx foi adicionado a SS. Temos ainda, necessariamente, que δ(s,y)δ(s,u)\delta(s, y) \leq \delta(s, u), visto que yy precede uu em pp.

Vamos agora adicionar uu a SS. Como ySy \notin S, vamos inevitavelmente ter que d[u]d[y]d[u] \leq d[y] - ora, mas como d[y]=δ(s,y)d[y] = \delta(s, y), como referido acima, temos que d[u] ⁣d[y]=δ(s,y)d[u] \leq \d[y] = \delta(s, y). Além disso, como yy aparece em pp antes de uu, temos que d[u]δ(s,y)δ(s,u)d[u] \leq \delta(s, y) \leq \delta(s, u), o que claramente contradiz o pressuposto de que d[u]δ(s,u)d[u] \neq \delta(s, u)!

Fica, então, provado o invariante do algoritmo - para todo o vértice vVv \in V, aquando da sua inserção em SS, d[v]=δ(s,v)d[v] = \delta(s, v)!

Finalmente, depois de apresentado o algoritmo, podemos mostrar porque é que, aqui, só podemos ter grafos sem arestas negativas:

Caminhos Mais Curtos - Dijkstra - Aresta Negativa

Aqui, claro, o invariante não se verifica, já que d(w)>δ(s,w)d(w) > \delta(s, w).

Algoritmo de Bellman-Ford

O algoritmo de Bellman-Ford resolve o caso geral do problema dos caminhos mais curtos de fonte única, onde os arcos podem ter peso negativo. Indica, no fim, a existência (ou não) de ciclos negativos, sendo que, caso não existam, pode produzir ainda o caminho mais curto e os custos associados a cada vértice.

O algoritmo em si tem um aspeto bastante mais simples que o de Dijkstra: trata-se de operações de relaxação sucessivas, passando por todas as arestas do grafo V1V - 1 vezes, com vista a atualizar gradualmente a estimativa de custo associado a cada vértice. Findas as relaxações, todas as arestas são percorridas, de modo a verificar se há algum ciclo negativo. O pseudocódigo é tal que:

BellmanFord(G, w, s)
  InitializeSingleSource(G, s)
  for each i in 1 .. |V| - 1 do
    for each (u, v) in E do
      Relax(G, u, v, w(u, v))
  for each (u, v) in E do
    if d[v] > d[u] + w(u, v) then
      return false
  return true

A complexidade temporal do algoritmo é Θ(V)+Θ(VE)+O(E)=Θ(VE)\Theta(V) + \Theta(VE) + O(E) = \Theta(VE) (de realçar que o Θ(V)\Theta(V) está associado a InitializeSingleSource). Como podemos notar, o algoritmo de Bellman-Ford é menos eficiente (do ponto de vista temporal) que o de Dijkstra, pelo que devemos recorrer a Dijkstra caso tenhamos a certeza que não há arestas negativas, a Bellman-Ford caso contrário.

Lema

Seja G=(V,E)G = (V, E) um grafo pesado dirigido, com fonte ss e função de pesos ww. Assumindo que não há ciclos negativos, após as VV iterações do primeiro loop do algoritmo de Bellman-Ford, temos que d[v]=δ(s,v),vVd[v] = \delta(s, v), \forall_{v \in V} tal que vv é atingível a partir de ss.

A prova baseia-se, claro, nas propriedades da relaxação. Comecemos por considerar qualquer vértice atingível a partir de ss, com p=(v0,v1,...,vk)p = (v_0, v_1, ..., v_k) (com v0=svk=vv_0 = s \wedge v_k = v) o caminho mais curto de ss a vv em GG. Temos que pp é simples - tem, no máximo, V1|V| - 1 arcos, já que um caminho mais curto não passará por um vértice mais que uma vez, caso contrário estaríamos necessariamente na presença de um ciclo negativo. Cada arco é relaxado V|V| vezes. Temos, então, de procurar provar que d[vi]=δ(s,vi),viVd[v_i] = \delta(s, v_i), \forall_{v_i \in V}, após a iteração ii do primeiro loop de Bellman-Ford sobre os arcos de GG, e que nunca se altera.

Provando por indução:

  • d[v0]=δ(s,v0)=0d[v_0] = \delta(s, v_0) = 0, obrigatoriamente, já que ss = v0v_0. Temos, claro, que não se altera.

  • assumindo que d[vi1]=δ(s,vi1)d[v_{i - 1}] = \delta(s, v_{i - 1}) após a iteração i1i - 1, temos que o arco (vi1,vi)(v_{i - 1}, v_i) será necessariamente relaxado na iteração seguinte (já que sabemos que agora o arco "anterior" em pp já está relaxado), pelo que d[vi]=δ(s,vi)d[v_i] = \delta(s, v_i) (e também não se alterará).

Esta prova foi retirada do livro que acompanha a cadeira, encontrando-se na página 673 do mesmo.

Como corolário do lema acima, podemos afirmar que só existe um caminho de ss a um qualquer vértice vVv \in V caso, finda a execução do algoritmo de Bellman-Ford d[v]+d[v] \neq +\infty.

Exemplo da aplicação do algoritmo

Abaixo podemos observar um exemplo da execução completa do algoritmo de Bellman-Ford (passos de aa a ee). A ordem de relaxação das arestas é, em cada iteração do loop, (t,x),(t,y),(t,z),(x,t),(y,x),(y,z),(z,x),(z,s),(s,t),(s,y)(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y):

Exemplo da aplicação do algoritmo

Na primeira iteração, temos, claro, que as únicas arestas cuja relaxação provoca diferença nas estimativas são as que saem de ss, já que são as únicas em que o vértice-fonte não tem estimativa ++\infty. Na segunda, podemos notar que já há mais alterações. Relaxar (t,x)(t, x) provoca alterações em xx, passando a sua estimativa para 1111 (que será já de seguida novamente alterada). Por outro lado, relaxar (t,y)(t, y) não provoca alterações ao custo de yy, já que a sua estimativa é 7<6+8=147 < 6 + 8 = 14. Relaxar (t,z)(t, z) provoca alterações (2\infty \to 2), tal como (y,x)(y, x) (11411 \to 4). Nenhuma das outras relaxações provoca diferenças. O resto das iterações do algoritmo não serão aqui detalhadas, visto que os passos a seguir são os mesmos (a diferença é quais as arestas cujo relaxamento nessa vez provoca diferenças).

Podemos, por fim, notar que o algoritmo devolve true, já que não ocorrem ciclos negativos!

Segundo Lema

Se G=(V,E)G = (V, E) não contém ciclos negativos, o algoritmo retorna true, e false caso contrário. A primeira parte da afirmação é fácil de provar - caso não existam ciclos negativos, então é impossível que, no fim do algoritmo, d[u]+w(u,v)d[u] + w(u, v) seja menor que d[v]d[v], visto que caso isso acontecesse o caminho não seria o mais curto. A segunda parte, contudo, pode parecer mais difícil à primeira vista. Procuremos uma prova por contradição, ou seja, admitir que o algoritmo retorna true mesmo havendo ciclos negativos. Ora, temos que Bellman-Ford só retorna true caso, (u,v)E,d[u]+w(u,v)d[v]\forall (u, v) \in E, d[u] + w(u, v) \geq d[v]. Dado que todas estas desigualdades são verificadas no último loop do algoritmo, podemos afirmar que as desigualdades ao longo do ciclo negativo (não confundir com durante todo o grafo) são dadas por:

i=0kd[vi]i=0kd[vi1]+i=0kw(vi1,vi)\sum_{i = 0}^k{d[v_i]} \leq \sum_{i = 0}^k{d[v_{i-1}]} + \sum_{i = 0}^k{w(v_{i-1}, v_i)}

Ora, estando perante um ciclo, teremos que i=0kd[vi1]=i=0kd[vi]\sum_{i = 0}^k{d[v_{i-1}]} = \sum_{i = 0}^k{d[v_i]} (cada vértice ocorre apenas uma vez em cada um dos somatórios). Este último ponto pode ser difícil de passar por escrito, por isso abaixo encontra-se uma imagem que pode ajudar a compreender esta afirmação:

Ciclos Negativos Bellman-Ford

Sendo eles iguais, podemos afirmar que:

0i=0kw(vi1,vi)0 \leq \sum_{i = 0}^k{w(v_{i-1}, v_i)}

Ora, isto claramente contradiz a existência de um ciclo negativo - ocorreria um ciclo negativo caso o resultado da soma fosse negativo. Conclui-se, então, que o algoritmo só retorna true caso não existam ciclos negativos!

Caminhos mais curtos em DAGs

O algoritmo para descobrir o caminho mais curto num DAG é ainda mais simples (e mais eficiente) que os de Dijkstra e Bellman-Ford. Sendo acíclico por definição, não nos teremos de preocupar com arestas negativas - caso estas existam, poderão provocar caminhos mais curtos, mas nunca ciclos negativos (visto que estamos a falar de DAGs).

A pedra basilar do algoritmo é a ordenação topológica dos vértices do grafo - com os vértices assim ordenados, o caminho mais curto será necessariamente relaxado de trás para a frente (seguindo a ordem topológica), pelo que nunca haverá o problema de termos de procurar relaxar arcos mais que uma vez (a prova desta afirmação encontra-se mais abaixo). O pseudocódigo do algoritmo é o seguinte:

DAG_ShortestPath(G, s)
    TopologicalSort(G)
    InitializeSingleSource(G, s)
    for each u in V, taken in topologically sorted order
        for each (u, v) in Adj[u]
            Relax(G, u, v, w(u, v))

Temos que a complexidade de TopologicalSort é Θ(V+E)\Theta(V + E) e que a de InitializeSingleSource é Θ(V)\Theta(V). Adicionalmente, o for loop exterior percorre todos os vértices (Θ(V)\Theta(V)), e cada aresta é percorridas apenas uma vez (Θ(E)\Theta(E)) ao longo do loop exterior; tendo em conta que Relax leva O(1)O(1) tempo, então a complexidade total é Θ(V+E)\Theta(V + E).

Exemplo da Aplicação do Algoritmo

Consideremos o grafo cuja ordenação topológica é a seguinte:

Ordenação Topológica

Temos que na figura acima foi já aplicado InitializeSingleSource. Consideremos que a ordem de passagem pelos vértices é A,B,C,D,EA, B, C, D, E. As arestas serão, então, relaxadas tal que:

Relaxação - Caminho mais Curto (Final)

Podemos, no exemplo acima, reparar que o caminho mais curto vai sendo gradualmente relaxado, vértice a vértice. Estando ordenados topologicamente, será impossível que o custo de um dado vértice possa, depois de explorado, vir a ser menor no futuro - os arcos estão de trás para a frente, é impossível voltar atrás. Contudo, nem todas as iterações têm de relaxar necessariamente uma aresta que faça parte do caminho mais curto - se tivéssemos, por exemplo, um vértice XX que viesse antes de AA na ordenação topológica, mas continuássemos a considerar AA como a fonte, a iteração que explorava as arestas que saíam de XX não contribuiria para o caminho mais curto, já que este vértice não é atingível a partir da fonte. Para provar que vVd[v]=δ(s,v)\forall_{v \in V} d[v] = \delta(s, v) no final do algoritmo, observemos o seguinte:

Prova da correção do Algoritmo

Como consideração inicial, podemos notar que se um vértice vv não é atingível a partir de ss, então d[v]=d[v] = \infty (tal como nos algoritmos de Dijkstra e Bellman-Ford). Suponhamos então que vv é atingível a partir de ss, com p=(v0,...,vk)p = (v_0, ..., v_k) um caminho mais curto de s=v0s = v_0 até v=vkv = v_k. Visto que os vértices serão exploradas pela sua ordem topológica, podemos garantir que os arcos que compõem pp são relaxados por ordem ((v0,v1),...,(vk1,vk)(v_0, v_1), ..., (v_{k-1}, v_k)). Pela última propriedade abordada na relaxação, podemos garantir que, para todas as iterações do loop do algoritmo, i=1,2,...,k,d[vi]=δ(s,vi)i = 1, 2, ..., k, d[v_i] = \delta(s, v_i).

Curiosidade

A título de curiosidade, podemos notar que o caminho mais longo entre dois vértices num grafo (assumindo que podemos atingir o vértice-destino a partir da fonte) pode ser obtido ao negar os pesos de todas as arestas, passar os ++\infty iniciais para -\infty e, na operação de relaxação, trocar os >> por <<.

O caminho mais longo pode ser particularmente útil para, entre outros, calcular um minorante para a quantidade de tempo/operações que uma dada tarefa vai levar - daí o nome pelo qual também é conhecido, caminho crítico.

Caminhos mais Curtos entre Todos os Pares

Nota

Esta secção tem a coautoria do João Rocha.

Os algoritmos de Dijkstra e Bellman-Ford, abordados acima, permitem-nos encontrar caminhos mais curtos de fonte única. Conhecendo-os, a nossa primeira intuição para descobrir os caminhos mais curtos entre todos os pares de vértices de um grafo poderá apenas passar por aplicar o algoritmo de Dijkstra V|V| vezes, com vértice-fonte a alterar para cada aplicação. A ideia não está errada, claro: funciona! Temos, contudo, um problema em mãos - continuamos a ter a limitação estudada acima (Dijkstra requer a ausência de arcos negativos). Será, então, interessante procurar uma solução alternativa que a remova, e é aqui que entra o algoritmo de Johnson, que curiosamente combina os algoritmos de Dijkstra e Bellman-Ford para chegar a este fim.

Algoritmo de Johnson

O algoritmo de Johnson permite-nos justamente remover a limitação acima mencionada. Para tal, usa uma estratégia: a repesagem de Johnson, baseada em Bellman-Ford, e acaba na aplicação de Dijkstra, usando todos os vértices como fonte. De realçar que a repesagem só é requerida caso haja pelo menos um arco negativo.

Durante o decorrer do algoritmo, são calculadas duas matrizes bidimensionais (onde cada dimensão tem tamanho V|V|):

  • DD, onde D(i,j)D(i, j) corresponde ao peso do caminho mais curto de ii a jj;

  • π\pi, onde π(i,j)\pi(i, j) corresponde ao predecessor de jj no caminho mais curto de ii a jj.

Vamos por partes:

Repesagem de Johnson

Tendo um grafo G=(V,E)G = (V, E), a repesagem de Johnson devolve um grafo G^=(V,E^)\hat{G} = (V, \hat{E}), onde E^\hat{E} corresponde a arcos "equivalentes" aos de EE, porém sem arcos negativos. Queremos, claro, que os caminhos mais curtos em G^\hat{G} sejam os mesmos que os de GG.

A intuição poderá levar-nos a pensar que uma maneira possível de chegar a G^\hat{G} é encontrar a aresta com peso mais negativo, pegar no seu módulo e somá-lo ao peso de todas os arcos de GG. A estratégia, contudo, não funciona para todos os casos - temos um contraexemplo abaixo:

Repesagem de Johnson - abordagem errada

Podemos observar, então, que esta abordagem acaba por penalizar caminhos mais curtos com mais arcos.

A abordagem correta passa, então, por adicionar um novo vértice, ss, ao grafo, e conectá-lo com arcos (s,v)(s, v) de peso 0 a todo o vértice vv de GG. De seguida, aplicar o algoritmo de Bellman-Ford ao grafo para descobrir as alturas de Johnson, hh, de cada vértice - correspondem ao peso do caminho mais curto de ss a cada vértice.

Obtidas as alturas de Johnson, temos que o peso de cada arco em G^\hat{G}, w^\hat{w}, é dado por*:

w^(i,j)=w(i,j)+h(i)h(j).\hat{w}(i, j) = w(i, j) + h(i) - h(j).

No fim, ao remover o vértice ss e respetivos arcos, ficamos com G^\hat{G}! A complexidade temporal da repesagem é, claro, O(VE)O(VE), tal como no usual Bellman-Ford.

* A razão pela qual a repesagem funciona não é trivial à primeira vista. A prova da sua correção encontra-se mais abaixo, pelo que podem preferir ler a mesma antes de ver o exemplo seguinte.

Exemplo da Repesagem de Johnson

Consideremos o grafo GG abaixo:

Repesagem de Johnson - exemplo

Após adicionar o vértice ss (e respetivas arestas), o grafo fica assim:

Repesagem de Johnson - exemplo - adicionado

Tenhamos, ainda, uma ordem arbitrária de relaxação de arcos, por exemplo (S,X),(S,U),(S,T),(S,V),(X,U),(U,V),(U,T),(V,X),(V,T)(S, X), (S, U), (S, T), (S, V), (X, U), (U, V), (U, T), (V, X), (V, T).

A primeira iteração de Bellman-Ford dará:

Repesagem de Johnson - exemplo - relaxação

A próxima iteração resulta num grafo igual, pelo que o algoritmo de Bellman-Ford termina aqui. Temos, então, que as alturas de Johnson dos vértices do grafo são:

  • h(X)=0h(X) = 0;
  • h(U)=0h(U) = 0;
  • h(T)=3h(T) = -3;
  • h(V)=2h(V) = -2;

Assim sendo, os novos pesos dos arcos de GG são:

  • w(X,U)=1+00=1w(X, U) = 1 + 0 - 0 = 1;
  • w(U,V)=2+0(2)=0w(U, V) = -2 + 0 - (-2) = 0;
  • w(U,T)=2+0(3)=1w(U, T) = -2 + 0 - (-3) = 1;
  • w(V,X)=2+(2)0=0w(V, X) = 2 + (-2) - 0 = 0;
  • w(V,T)=1+(2)(3)=0w(V, T) = -1 + (-2) - (-3) = 0;

Assim, temos que G^\hat{G} é tal que:

Repesagem de Johnson - exemplo - resultado

De realçar que nenhum arco tem agora peso negativo!

Por fim, aplicamos Dijkstra a cada um dos vértices do grafo (não mostrado aqui, é igual à aplicação normal de Dijkstra), e obteríamos os caminhos mais curtos no grafo para todos os pares! Cada linha ii da matriz DD corresponde, claro, à aplicação de Dijkstra a G^\hat{G} com ii como fonte.

A repesagem de Johnson assenta em dois pilares:

  • GG contém um ciclo negativo se e só se G^\hat{G} contém um ciclo negativo;

  • Se pp é um caminho mais curto de uu a vv em GG, então também o é em G^\hat{G}.

Prova do primeiro ponto

Admita-se que GG tem um ciclo v0,v1,v2,,vk1,vkv_0, v_1, v_2, \cdots , v_{k-1}, v_k (em que vk=v0v_k = v_0). Temos que:

i=0k1w(vi,vi+1)=i=0k1w(vi,vi+1)+h(i+1)h(i)=i=0k1w(vi,vi+1)+i=0k1h(i+1)i=0k1h(i)=i=0k1w(vi,vi+1)\sum_{i=0}^{k-1} w(v_i, v_{i+1}) = \sum_{i=0}^{k-1} w^\wedge(v_i, v_{i+1}) + h(i+1) - h(i) = \sum_{i=0}^{k-1} w^\wedge(v_i, v_{i+1}) + \sum_{i=0}^{k-1} h(i+1) - \sum_{i=0}^{k-1} h(i) = \sum_{i=0}^{k-1} w^\wedge(v_i, v_{i+1})

Ou seja, o peso de qualquer ciclo em GG é igual ao peso de qualquer ciclo em GG^\wedge. Desta forma, a existência de um ciclo negativo em qualquer um dos grafos equivale à existência de um ciclo negativo no outro grafo.

Prova do segundo ponto

Resta agora provar o segundo ponto acima proposto. Comecemos por notar que, com p=(v0,...,vn)p = (v_0, ..., v_n), um caminho mais curto em GG, temos que:

w^(p)=i=0n1w^(vi,vi+1)w^(p)=i=0n1w(vi,vi+1)+h(vi)h(vi+1)w^(p)=i=0n1w(vi,vi+1)+i=0n1h(vi)h(vi+1)w^(p)=w(p)+h(v0)h(vn)\hat{w} (p) = \sum_{i = 0}^{n-1} \hat{w}(v_i, v_{i+1})\\ \hat{w} (p) = \sum_{i = 0}^{n-1} w(v_i, v_{i+1}) + h(v_i) - h(v_{i+1})\\ \hat{w} (p) = \sum_{i = 0}^{n-1} w(v_i, v_{i+1}) + \sum_{i = 0}^{n-1} h(v_i) - h(v_{i+1})\\ \hat{w} (p) = w(p) + h(v_0) - h(v_n)

A passagem de i=0n1h(vi)h(vi+1)\sum_{i = 0}^{n-1} h(v_i) - h(v_{i+1}) para h(v0)h(vn)h(v_0) - h(v_n) é feita através de somas telescópicas - teríamos h(v0)h(v1)+h(v1)h(v2)+...h(vn1)+h(vn1)h(vn)=h(v0)h(vn)h(v_0) - h(v_1) + h(v_1) - h(v_2) + ... -h(v_{n-1}) + h(v_{n-1}) - h(v_n) = h(v_0) - h(v_n).

Suponhamos agora, por contradição, que pp é um caminho mais curto de v0v_0 a vnv_n em GG mas não em G^\hat{G}. Assim, teríamos um caminho, pp', que teria peso menor que pp em G^\hat{G} a ligar v0v_0 a vnv_n. Teríamos, então:

w^(p)<w^(p)w(p)+h(v0)h(vn)<w(p)+h(v0)h(vn)w(p)<w(p)\hat{w}(p') < \hat{w}(p)\\ w(p') + h(v_0) - h(v_n) < w(p) + h(v_0) - h(v_n)\\ w(p') < w(p)

Ora, chegámos então a w(p)<w(p)w(p') < w(p). Tínhamos, contudo, começado por afirmar que pp é um caminho mais curto de v0v_0 a vnv_n em GG. Partindo dessa premissa, não pode haver nenhum caminho que ligue v0v_0 a vnv_n em GG, pelo que estamos perante uma contradição, e o segundo ponto fica então provado.

Depois da repesagem de Johnson, o grafo já não apresenta arcos negativos. Podemos, então, proceder à aplicação do algoritmo de Dijkstra em cada vértice para determinar os caminhos mais curtos entre todos os pares de vértices.

Resta, então, notar que a complexidade temporal do algoritmo é O(V(V+E)logV)O(V (V + E) \log V), predominando, portanto, a complexidade de Dijkstra pelos V|V| vértices.