Data de Aula: 21-Mai-2003
Redator: Carlos R. Senna - RA
022.248
Definição de um caminho mais curto.
Subestrutura ótima de um caminho mais curto.
Ciclos e arestas de peso negativo.
Nessa ata são apresentadas opções para resolver o problema de encontrar os caminhos mais curtos num grafo, como por exemplo, encontrar a melhor rota dentre as várias possibilidades de ligações entre duas cidades. Definimos o que é um caminho mais curto entre dois vértices, apresentamos uma subestrutura ótima de um caminho mais curto, abordamos os pesos das arestas, ciclos que possam ocorrer num caminho mais curto, e como podemos representar caminhos mais curtos na forma de um grafo. Resulta que resolver o problema entre dois vértices acaba sendo equivalente em termos de complexidade a resolvê-lo para todos os pares (s,v) de vértices, onde s é fixo. Por isso chamamos este problema de "caminhos mais curtos de origem única".
Para resolver o problema de caminhos mais curtos de origem única, mostramos o algoritmo de Bellman-Ford. Esse algoritmo usa a técnica de relaxar as arestas, diminuindo progressivamente uma estimativa no peso de um caminho mais curto da origem até cada vértice, até alcançar o peso real do caminho mais curto.
Para um grafo orientado ponderado G = (V, E), com função peso w:E → R mapeando arestas para pesos de valores reais. O peso do caminho p = < v0, v1, ..., vk > é o somatório dos pesos de suas arestas constituintes:
Definimos o peso do
caminho mais curto desde u até v por:d
(u,v) = min{w(p): u ® v} se existe um caminho de u até v, ou Infinito em caso contrário.Um caminho mais curto desde o vértice u até o vértice v, é então definido como qualquer caminho p com peso w(p) =
d(u,v). Ou seja, qualquer caminho cuja soma dos pesos seja a menor possível.Obs.: ® Está sendo substituindo a seta torta com p em cima.
(Veja mais sobre caminho ao final da ata).
Focalizaremos nosso estudo sobre o problema de caminhos mais curtos de origem única, onde dado um grafo G = (V, E), queremos encontrar um caminho mais curto desde um determinado vértice de origem s pertencente a V até todo vértice v pertencente a V.
Os algoritmos que resolvem o problema de origem única podem resolver também problemas variantes como:
Caminhos mais curtos de destino único;
Caminho mais curto de par único;
Caminhos mais curtos de todos os pares.
(Prof. Meidanis destacou que assintoticamente a complexidade para encontrar o caminho mais curto entre dois vértices é a mesma para encontrar os caminhos mais curtos para todos os vértices).
Ivan perguntou se o problema de caminhos mais curtos poderia ser resolvido por Programação Dinâmica e Prof. Meidanis respondeu que trata-se de uma estratégia gulosa.
Um caminho mais curto p = < v0, v1, ..., vk > tem como propriedade que qualquer trecho seu da forma < vi, vi+1, ..., vj > é também um caminho mais curto. Essa propriedade da subestrutura ótima permite a aplicação do método guloso nos algoritmos que veremos para resolver o problema do caminho mais curto.
Thiago perguntou sobre o significado do símbolo (seta curva com um p em cima), usada nas definições desse capítulo do livro. Prof. Meidanis respondeu que indica "que existe uma caminho, ou trecho de caminho, entre os vértices relacionados à seta curva).
Em algumas instâncias do problema de caminhos mais curtos de única origem, pode haver arestas cujos pesos são negativos. Se o grafo não contém um ciclo de peso negativo acessível a partir da origem, então para todo vértice, o peso do caminho mais curto permanece bem definido, mesmo se houver um valor negativo em uma ou mais arestas. Contudo, se existe um ciclo de peso negativo acessível a partir da origem, os pesos de caminhos mais curtos não são bem definidos. Sempre será possível encontrar um caminho mais curto através de uma nova passada pelo ciclo negativo. Se existe um ciclo de peso negativo em algum caminho a partir da origem s até v, definimos d(s,v) = -infinito, conforme ilustra a figura abaixo.
Na figura mostramos dentro de cada vértice o peso de seu caminho mais curto a partir da origem s. Como os vértices e e f formam um ciclo de peso negativo acessível a partir de s, eles têm peso -infinito. Como o vértice g também é acessível através de f, ele também tem peso de caminho mais curto -infinito. Assim concluímos que um caminho mais curto não pode conter ciclos de peso negativo.
Observando um pouco mais a questão dos ciclos é possível verificar que o caminho mais curto não pode conter também um ciclo de peso não negativo, pois a remoção do ciclo produz um caminho com os mesmos vértices de origem e destino com peso menor ou igual ao do caminho que contém o ciclo.
Nesse momento Alexandro questionou se a retirada de um ciclo positivo não causaria um " buraco" no grafo. Prof. Meidanis construiu o grafo abaixo e fez as seguintes considerações.
A indicação com as setas mostra um caminho, onde temos um ciclo entre os vértices B e C. Podemos percorrê-lo de várias maneiras. ABCD, ABCBCD, etc. O ciclo BCB pode ser retirado do caminho. Alternativamente, o ciclo CBC pode ser retirado. É importante observar que retiramos o ciclo do caminho e não do grafo.
Dado um grafo G = (V, E), mantemos para cada vértice v ∈ V um predecessor p[v] que é outro vértice ou NIL. Os algoritmos desse capítulo definem os atributos de π de forma que a cadeia de predecessores com origem em um vértice v seja percorrida ao contrário ao longo de um caminho mais curto da origem s até o vértice v. Estamos interessados no subgrafo predecessor Gπ = (Vπ , Eπ ) induzido pelos valores de π . Definimos o conjunto de vértices Vπ , como o conjunto de vértices de G com predecessores não NIL, mais a origem s:
Vπ = { v ∈ V : p[v] ≠ NIL} ∪ {s},
E o conjunto de arestas orientadas Eπ como sendo o conjunto de arestas induzidas pelos π valores correspondentes aos vértices em Vπ .
Eπ = {(π[v], v) ∈ E : v ∈ Vp - {s}}.
Os π valores produzidos pelos algoritmos apresentados nesse capítulo do livro texto, formam Gπ uma árvore de caminhos mais curtos, sendo importante destacar que nem os caminhos mais curtos são únicos, nem as árvores de caminhos mais curtos são únicas para um determinado grafo, conforme apresentado na figura a seguir.
Para o grafo orientado ponderado da figura a, temos duas árvores de caminhos mais curtos com raiz na origem s, mostradas pelas figuras b e c através das arestas sombreadas.
Os algoritmos desse capítulo usam a técnica do relaxamento das arestas. Para cada vértice v ∈ V, mantemos um atributo d[v] que é o limite superior sobre o peso de um caminho mais curto desde a origem s até v. Chamamos d[v] uma estimativa de caminho mais curto. Iniciamos as estimativas e os predecessores através do procedimento:
Relaxar uma aresta (u, v) é testar se podemos melhorar o caminho mais curto para v através de u e, nesse caso, atualizar d[v] e p [v]. O procedimento RELAX abaixo executa uma etapa de relaxamento numa aresta.
O algoritmo de Bellman-Ford resolve o problema do caminho mais curto de única origem para o caso mais geral, no qual os pesos das arestas podem ser negativos. Dado um grafo orientado ponderado G = (V, E) com origem em s e função peso w:E → R, o algoritmo retorna FALSE quando encontra um ciclo de peso negativo indicando que não existe solução, ou retorna TRUE indicando que produziu os caminhos mais curtos e seus pesos. O algoritmo usa a técnica do relaxamento, diminuindo progressivamente a estimativa d[v] no peso de um caminho mais curto.
O algoritmo começa iniciando as estimativas d[v] nos pesos dos caminhos mais curtos com infinito e os predecessores π [v] com NIL, através do procedimento INITIALIZE-SINGLE-SOURCE. Nas linhas 2 a 4 tenta relaxar todas as arestas de todos os vértices. E finalmente verifica a existência de um ciclo de peso negativo nas linhas de 5 a 7.
A figura a seguir mostra a execução do algoritmo de Bellman-Ford sobre um grafo de 5 vértices.
A figura a mostra o grafo após a execução do procedimento INITIALIZE-SINGLE-SOURCE. As figuras b até e mostra as sucessivas passagem das linhas 2 a 4 relaxando progressivamente as arestas. Na figura e temos os valores finais para d e π . Nesse exemplo o algoritmo retorna TRUE, pois não há ciclos de pesos negativos.
O algoritmo Bellman-Ford é executado no tempo O(V E). A inicialização através de INITIALIZE-SINGLE-SOURCE demora Q (V), cada uma das passagens sobre as arestas nas linhas 2 a 4 demora o tempo Q (E), e o ciclo para verificar ciclos de peso negativo das linhas 5 a 7 demora o tempo de Q (E).
Durante o transcorrer da aula em vários tópicos a expressão caminho causou dúvidas sobre a sua definição. Prof. Meidanis informou que as definições usuais são:
Um caminho de comprimento k de um vértice u até um vértice u' em um grafo G = (V, E), é uma seqüência < v0, v1, ..., vk > de vértices tais que u = v0 , u' = vk e (vi-1, ,vi) para i = 1,2,...k, onde todos os vértices do caminho são distintos.
Um passeio é um caminho onde vértices e arestas podem ser repetidas.
Uma trilha é um caminho onde apenas os vértices podem ser repetidos.
As definições apresentadas pelo livro texto (no Apêndice C pag. 854), são diferentes. O livro chama de caminho simples o caminho usual, e de caminho o que é chamado de passeio. Todo o conteúdo do livro toma as definições do apêndice como base.
(livro texto) Cormen, T.H.;Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos. Tradução da 2ª edição americana Teoria e Prática, 2002.