Consideraremos aqui The all pairs shortest path problem, ou seja: dados: um grafo D=(V,A); uma função `comprimento' len de A nos inteiros; encontra: um passeio mínimo de u a v, para todo par u e v de vértice v do grafo D ou um ciclo negativo em D.
Observação. A descrição dos algoritmos abaixo foram extraídas do livro:
R.E. Tarjan, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, Philadelphia, Pennysylvania, 1983.
Seja D=(V,A) um grafo e s um vértice de D e len uma função `comprimento' de A nos inteiros. Consideraremos agora o problema de determinar um passeio mínimo entre todos os pares de vértices de um grafo. O grafo pode ter arcos de comprimento negativo, mas não deve conter ciclos negativos. Apresentaremos dois algoritmos para este problema. O primeiro, que é mais apropriado para grafos `esparsos', combina busca em largura e o Algoritmo de Dijkstra. O segundo, que é mais apropriado para grafos `densos', usa programação dinâmica.
Se o grafo D não contém arcos de comprimento negativo, nós podemos
encontrar todos os passeios mínimos em tempo O(nm log n)) através de
n iterações do Algoritmo de Dijkstra para cada vértice fonte s
de D. Mesmo que existam arcos de comprimento negativo nós podemos obter
um algoritmo com a mesma complexidade de tempo fazendo que, em um
pré-processamento, todos os arcos fiquem com comprimento não-negativo.
J. Edmonds e R. Karp obtiveram a transformação apropriada. Primeiro
acrescentamos a D um novo vértices s e arcos (s,v) de
comprimento zero para cada vértice v de D. Então, para cada vértice v do grafo nós calculamos o comprimento distância(v) de um passeio mínimo de s a v neste novo grafo. Este passo pode ser feito com o Algoritmo de Bellman-Ford-Moore em tempo O(nm). Finalmente, nós definimos um novo comprimento
len'para cada arco (u,v) por
Teorema 1.
Para cada arco (u,v), len'(u,v) é não-negativo. Ademais,
para todo passeio P de um vértice s a um vértice t satisfaz
Prova. Usando a caracterização de árvores de caminhos mínimos pode-se verificar a primeira parte do teorema. A segunda parte do teorema pode ser demonstrada por indução no número de arcos de P. Talvez seja bom termos em mente os seguintes teoremas.
[Teorema 2. Seja s um vértice de um grafo D tal que todos os vértices de D são acessíveis a partir de s. Então vale uma, e apenas uma, das seguintes afirmação:
Se T é uma árvore (ou arborescência) geradora de D com raiz s e v é um vértice de D, nós definimos dist[v] como sendo a distância de s a v em T. O algoritmo que descreveremos é baseado no seguinte teorema.
Teorema 3. (Caracterização de árvores de caminhos mínimos)
T é uma árvore de caminhos mínimos se e
somente se, para cada arco (u,v) de D vale que
Pelo Teorema 1, a transformação proposta por Edmonds e Karp faz com que todos os novos comprimentos sejam não-negativos e preserva passeios mínimos. Logo, podemos agora encontrar um passeio mínimo entre cada para de vértices aplicando o Algoritmo de Dijkstra n vezes no grafo D com os novos comprimentos de
de seus arcos. Assim, combinando o Algoritmo de Bellman-Ford-Moore e Dijkstra podemos encontrar passeios mínimos entre todos os pares de vértices de D em tempo O(nm log n). O algoritmo resultante é remomendado para grafos èsparsos' já que a sua complexidade depende do número de arcos do grafo. O algoritmo de veremos agora para encontrar um passeio mínimo entre cada para de vértices de um grafo é baseado em programação dinâmica e foi proposto independentemente por R.W. Floyd e S. Warshall.
O Algoritmo de Floyd-Warshall mantém uma distância tentativa
dist[u,v] para cada par de vértices u e v. O algoritmo
processa os vértices do grafo, um por vez, mantendo o invariante
LABELING STEP (Floyd-Warshall). Se dist[u,u] < 0, pare, pois existe um ciclo negativo no grafo. Caso contrário, para cada par de vértices v e w tal que
Teorema 4. O Algoritmo de Floyd-Warshall calcula as distâncias entre todos os pares de vértices de D e constrói árvores de caminhos mínimos para todo vértice de D. Ademais, se durante a execução do algoritmo dist[u,u] <0 para algum vértice u então o grafo D contém um ciclo negativo
Prova. Suponha que durante a execução do algoritmo mantemos
um passei passeio[u,v] para cada par de vértices tal que
dist[u,v] é finita. Inicialmente defina
passeio[u,v]= (u,v) se (u,v) é um arco,
passeio[u,v]= (u) se u=v, e
passeio[u,v]= NULL caso contrário.
Quando trocamos dist[v,w] por
dist[v,u] + dist[u,w], nós também trocamos passeio[v,w] por
(passeio[v,u] - {u}) & passeio[u,w]. O algoritmo mantém os seguintes invariantes: