MAC0338   Análise de Algoritmos

Página preparada por Paulo Feofiloff para a disciplina MAC 338 Análise de Algoritmos, versão 1999.
O endereço original desta página é http://www.ime.usp.br/~pf/mac338/aulas/dijkstra.htm.

 

Caminhos de peso mínimo

Esta página é um resumo do capítulo 25 (somente algoritmo de Dijkstra) de CLR.

 

Caminhos w-mínimos

Suponha que cada aresta (u,v) de um grafo tem um peso w(u,v). Para qualquer caminho C, vamos denotar por w(C) o peso do caminho, ou seja, a soma dos pesos das arestas que formam o caminho.  Dados vértices s e t, um caminho C de s a t tem peso mínimo (ou é w-mínimo) se

w(C) <= w(C')

para qualquer caminho C' de s a t.

PROBLEMA: Dado um grafo, dois vértices s e t, e uma função w que atribui um peso a cada aresta, encontrar um caminho de peso mínimo de s a t.

O problema faz sentido com qualquer peso real (positivo ou negativo), mas fica mais difícil na presença de pesos negativos. Vamos supor, portanto, que

w(u,v) >= 0

para cada aresta (u,v).

 

Exercícios

  1. Suponha dado um grafo com vértices 1, 2, . . . . , n. Suponha que todas as arestas são da forma (j,i), com i < j. Suponha que cada aresta (u,v) tem um peso w(u,v), que pode ser positivo ou negativo.
    Escreva um algoritmo que encontre um caminho de peso mínimo de um vértice s a um vértice t.  Quanto tempo o seu algoritmo consome?

  2. Suponha dado um grafo com vértices 1, 2, . . . . , n. Suponha que todas as arestas são da forma (j,i), com i < j. Suponha que cada aresta (u,v) tem um peso w(u,v), que pode ser positivo ou negativo. A altura de um vértice u é o peso de um caminho de peso mínimo de u até o vértice 1. (Atenção: eu disse "de u até 1".)

    Escreva um algoritmo que resolva o seguinte problema: Encontrar a altura de cada um dos vértices do grafo.

 

Algoritmo de Dijkstra

A experiência mostra que não adianta preocupar-se apenas com os caminhos de s a t: é preciso considerar também os caminhos que vão de s aos demais vértices do grafo. Ou seja, é preciso encontrar uma árvore geradora com raiz s que tenha a seguinte propriedade: para cada vértice v, o único caminho de s a v na árvore é um caminho de peso mínimo (dentre os que começam em s e terminam em v).

Eis um algoritmo que resolve o problema quando não há arestas de peso negativo. O algoritmo recebe um grafo com vértices 1, 2, . . . . , n e arestas definidas por listas de adjacência Adj. Recebe também um vértice s e um peso não-negativo w(u,v) para cada aresta (u,v). O algoritmo determina um caminho w-mínimo de s a cada um dos demais vértices; os caminhos são representados por um vetor de predecessores.

 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
 DIJKSTRA (n, Adj, w, s)
  para u := 1 até n faça
    cor[u] := BRANCA
    d[u] := INFINITO
    pred[u] := 0
  d[s] := 0
  Q := CRIE-FILA ()
  enquanto Q não está vazia faça
    u := RETIRE-MÍNIMO (Q)
    cor[u] := NEGRA
    para cada v em Adj[u] faça
      se cor[v] = BRANCA  e  d[u]+w(u,v) < d[v] então
        d[v] := d[u]+w(u,v)
        pred[v] := u
  devolva pred

O comando CRIE-FILA () cria uma "fila" com todos os vértices. A prioridade dos vértices na fila é dada pelo vetor d. Os detalhes de implementação da fila ficam por conta do leitor. O comando RETIRE-MÍNIMO (Q) retira de Q um vértice u para o qual d[u] é mínimo. A alteração do valor de d[v] na linha 12 pode afetar a estrutura da fila; isso deve ser levado em conta quando a fila for implementada pra valer.

Para entender por que o algoritmo funciona corretamente, é preciso observar que no início de cada iteração valem as seguintes propriedades:

  1. todo vértice em Q é BRANCO e todo vértice BRANCO está em Q;
  2. para todo vértice x existe um caminho de s a x cujo peso é d[x]
    (portanto, d[x] é sempre uma estimativa "por cima" da "distância" de s a x);
  3. w(C) >= d[x] para todo caminho C que começa em s e termina em um vértice NEGRO
    (ou seja, se x é NEGRO então d[x] é a "distância" correta de s a x);
  4. w(C) >= d[u] para todo caminho que começa em s, termina em um vértice BRANCO u e
    não tem outros vértices BRANCOs além de u.

Resumo de 2,3,4:  d[x] é o peso de um caminho de peso mínimo dentre os que não têm vértices BRANCOs exceto talvez o último.

(Eu acho mais fácil entender o algoritmo através dessas propriedades que através da demonstração do nosso guru CLR.)

A operação nas linhas 11-13 é conhecida como relaxação da aresta (u,v). A idéia é óbvia: se existe um caminho de peso d[u] de s até u então também existe um caminho de peso d[u]+w(u,v) de s até v.

 

Exercícios

  1. Critique a seguinte versão do algoritmo de Dijkstra: 
              DIJKSTRA (n, Adj, w, s)
          para u := 1 até n faça
             cor[u] := BRANCA
             d[u] := INFINITO
             pred[u] := 0
          d[s] := 0
          Q := CRIE-FILA () // coloca todos os vértices na fila
          enquanto Q não está vazia faça
             u := RETIRE-MÍNIMO (Q)
             para cada v em Adj[u] faça
                se cor[v] = BRANCA e d[u]+w(u,v) < d[v] então
                   d[v] := d[u]+w(u,v)
                   pred[v] := u
                   cor[v] := CINZA  // atenção!
             cor[u] := NEGRA
          devolva pred


  2. Critique a seguinte versão do algoritmo de Dijkstra: 
              DIJKSTRA (n, Adj, w, s)
          para u := 1 até n faça
             cor[u] := BRANCA
             d[u] := INFINITO
             pred[u] := 0
          d[s] := 0
          Q := CRIE-FILA (s) // coloca só s na fila
          enquanto Q não está vazia faça
             u := RETIRE-MÍNIMO (Q)
             para cada v em Adj[u] faça
                se cor[v] = BRANCA e d[u]+w(u,v) < d[v] então
                   d[v] := d[u]+w(u,v)
                   pred[v] := u
                   INSERE-NA-FILA (Q, v)  // atenção!
             cor[u] := NEGRA
          devolva pred

    O comando INSERE-NA-FILA(Q,v) insere v na fila Q somente se v ainda não estiver lá.

  3. Critique a seguinte versão do algoritmo de Dijkstra. Esta versão promete devolver a distância de s a t: 
              DIJKSTRA (n, Adj, w, s, t)
          para u := 1 até n faça
             d[u] := INFINITO
          d[s] := 0
          Q := CRIE-FILA (s) // coloca todos os vértices na fila
          enquanto Q não está vazia faça
             u := RETIRE-MÍNIMO (Q)
             para cada v em Adj[u] faça
                se d[u]+w(u,v) < d[v] então
                   d[v] := d[u]+w(u,v)
                   se v = t então      // atenção!
                      devolva d[t]     // atenção!


 

Eficiência do algoritmo

Comece considerando a possibilidade de implementar Q em uma fila SEM prioridades. Faça busca linear para achar o mínimo. Suponha matriz de adjacência no lugar de Adj. Temos n iterações. Cada iteração gasta n em retirar o mínimo. Cada vértice sai de Q e fica negro uma só vez. Logo, cada linha da matriz é examinada apenas uma vez. Temos aí n2. Total: n2+n2.

Se usarmos listas de adjacência, teremos O(n2+m).

 

Exercícios

  1. [CLR 25.2-3]   Que acontece se o algoritmo DIJKSTRA for interrompido quando Q tem apenas um elemento?

  2. Afirmamos acima que 4 propriedades valem no início de cada iteração do algoritmo DIJKSTRA. Mostre que as propriedades são, de fato, válidas.

  3. O algoritmo de Dijkstra funciona corretamente sobre grafos não-simétricos (ou é preciso que o grafo seja simétrico)?

  4. Escreva uma implementação mais detalhada do algoritmo DIJKSTRA. Use um heap para implementar a fila Q.

  5. Digamos que a distância de um vértice s a um vértice t é o peso de um caminho de peso mínimo dentre os que vão de s a t. Escreva um algoritmo que determine a distância de s a cada um dos vértices do grafo. Procure escrever o algoritmo mais curto e eficiente possível.

  6. [CLR 25.2-2]   Mostre que o algoritmo DIJKSTRA pode produzir resultados errados se w(u,v) < 0 para alguma aresta (u,v).

  7. [IP 436]   Suponha queremos um caminho de s a t que tenha peso máximo (suponha que os pesos das arestas são não-negativos). É possível resolver o problema trocando MÍNIMO por MÁXIMO na linha 8 do algoritmo DIJKSTRA? (É claro que esse ajuste deve ser acompanhado de outros ajustes óbvios nas linhas 3 e 11.)

  8. [CLR 25.2-4]   Suponha que a cada aresta (u,v) de um grafo está associado um número c(u,v) entre 0 e 1. Este número representa a "confiabilidade" da aresta (u,v), ou seja, a probabilidade de que a aresta não vai "quebrar" (isto é, "falhar", "desaparecer"). Dados vértice r e s, encontre um caminho de s a t que tenha mínima confiabilidade de s a t. Encontre um caminho de s a t que tenha máxima confiabilidade de s a t.

 

Versão seca do algoritmo

As cores ajudam a entender o funcionamento do algoritmo mas são supérfluas. O teste da cor de v na linha 11 também é supérfluo (ainda que possa contribuir para fazer o algoritmo um pouquinho mais rápido).

DIJKSTRA-SECO (n, Adj, w, s)
  para u := 1 até n faça
    d[u] := INFINITO
    pred[u] := 0
  d[s] := 0
  Q := CRIE-FILA ()
  enquanto Q não está vazia faça
    u := RETIRE-MÍNIMO (Q)
    para cada v em Adj[u] faça
      se d[u]+w(u,v) < d[v] então
        d[v] := d[u]+w(u,v)
        pred[v] := u
  devolva pred

Mostre que esta versão (sem o teste de cor antes de "d[u]+w(u,v)<d[v]") não produz caminhos de peso mínimo quando há arestas de peso negativo.

 

Exercícios

  1. Escreva um algoritmo que encontre um caminho de peso máximo de um vértice s a um vértice t em um grafo acíclico com pesos nas arestas (os pesos podem ser negativos).  Quanto tempo o seu algoritmo consome?

 

 

 

Last modified: Fri Sep 10 08:49:27 EST 1999
Paulo Feofiloff
IME-USP

Valid HTML 4.0!