Algoritmos para Grafos, via Sedgewick | Índice remissivo
Esta página introduz o problema dos caminhos de custo mínimo em digrafos com custos nos arcos. Vamos supor que todos os custos são não negativos (o problema faz sentido sem essa hipótese, mas fica bem mais difícil).
(Esta página é um resumo das seções 21.0 e 21.1 (Underlying Principles), p.265-280, do capítulo 21 (Shortest Paths) do livro de Sedgewick.)
Num digrafo com custos nos arcos, o custo de um caminho é a soma dos custos dos arcos do caminho. Um caminho C é mínimo se não existe outro caminho com mesma origem e mesmo término que C mas mais barato que C. Por causa da presença dos custos, este conceito é mais geral que o conceito de caminho mínimo definido em outra página.
A distância de um vértice s a um vértice t é o custo de um caminho mínimo de s a t. (Dada a presença dos custos, esse conceito é mais geral que o conceito de distância definido em outra página.) Em outras palavras, a distância de s a t é d se e somente se (1) existe um caminho de custo d de s a t e (2) nenhum caminho de s a t tem custo menor que d.
Se o digrafo é um grafo, a distância de s a t é igual à distância de t a s. Portanto, podemos usar a expressão "distância entre s e t" nesse caso.
Vamos supor, ao tratar de caminhos mínimos e distâncias, que o custo de cada arco é um número
não negativo.
Assim, a distância de um vértice s a um vértice t fica bem definida sempre que existe algum caminho de s a t. (Se não existe caminho algum, podemos dizer que a distância de s a t é infinita.) [O problema do caminho mínimo em digrafos que têm arcos de custo negativo é muito importante, mas bem mais difícil. No caso de digrafos simétricos, ele está relacionado com o célebre problema do caminho hamiltoniano.]
Digrafos com custos não negativos têm a seguinte propriedade crucial: qualquer segmento de um caminho mínimo é um caminho mínimo.
Outro aspecto dessa mesma propriedade: a menos que o digrafo tenha um ciclo de custo nulo, todo caminho mínimo é simples. Mesmo que o digrafo tenha ciclos de custo nulo, é verdade que para todo vértice s e todo vértice t
existe um caminho simples de s a t cujo custo é igual à distância de s a t
(desde que essa distância seja finita). Podemos nos restringir, portanto, a caminho mínimos que são simples.
Nosso problema básico é o seguinte:
Problema do Caminho Mínimo com Origem e Término Fixos (Source-sink Shortest Path Problem): Dados vértices s e t de um digrafo com custos não negativos nos arcos, encontrar um caminho mínimo simples de s a t.
(É claro que o problema só tem solução se t pode ser alcançado a partir de s, ou seja, se existe um caminho de s a t.) A experiência mostra que é mais prático tratar de um problema mais geral:
Problema dos Caminhos Mínimos com Origem Fixa (Single-source Shortest Paths Problem): Dado um vértice s de um digrafo com custos não negativos nos arcos, encontrar, para cada vértice t que pode ser alcançado a partir de s, um caminho mínimo simples de s a t.
Todos os algoritmos para esses problemas exploram a seguinte propriedade básica:
Propriedade Triangular: Para quaisquer vértices x, y e z de um digrafo com custos não negativos nos arcos, tem-sed(x,z) ≤ d(x,y) + d(y,z) ,
sendo d(i,j) a distância de i a j.
| A | B | C | D | |
| A | 0 | 53 | 54 | 48 |
| B | 53 | 0 | 18 | 101 |
| C | 54 | 18 | 0 | 12 |
| D | 48 | 101 | 12 | 0 |
As distâncias estão corretas? Refaça a tabela se necessário. Faça outra tabela que indique em cada posição (x,y) qual o primeiro vértice no caminho mínimo de x para y. (Veja figura 21.4, p.270, de Sedgewick.)
Dado um vértice s de um digrafo G com custos não negativos nos arcos, uma arborescência de caminhos mínimos (= shortest-paths tree = SPT) com raiz s é uma arborescência em G que tem a seguinte propriedade: para todo vértice t de G que pode ser alcançado a partir de s,
o único caminho de s a t na arborescência é um caminho mínimo em G.
Vou usar a sigla em inglês — SPT — para me referir a uma arborescência de caminhos mínimos. É claro que qualquer SPT pode ser representada por um vetores de pais.
Uma SPT pode ser vista como uma solução do Problema dos Caminhos Mínimos Com Origem Fixa. Por isso mesmo, esse problema pode ser reformulado assim:
Problema da SPT: Dado um vértice s de um digrafo com custos não negativos nos arcos, encontrar uma SPT com raiz s no digrafo.
A tabela define um digrafo com custos nos arcos. (Este é o exemplo da figuras 21.1, p.266, e 21.3, p.269, do Sedgewick.)
0-1 .41 1-2 .51 2-3 .50 4-3 .36 3-5 .38 3-0 .45 0-5 .29 5-4 .21 1-4 .32 4-2 .32 5-1 .29
A tabela abaixo dá a distância de 0 a cada um dos demais vértices. Também especifica caminhos mínimos de 0 a cada um dos demais vértices.
0 .0 0 1 .41 0-1 2 .82 0-5-4-2 3 .86 0-5-4-3 4 .50 0-5-4 5 .29 0-5
Eis uma SPT com origem 0 representados por um vetores de pais:
v 0 1 2 3 4 5
parent[v] 0 0 4 4 5 0