"Highways, telephone lines, electric power systems, computer chips,
water delivery systems, and rail lines: these physical networks, and
many others, are familiar to all of us. In each of these problem settings,
we
often wish to send some good(s) (vehicles, messages, electricity, or
water)
from one point to another, typically as efficiently as possible --
that is, along a shortest route or via some minimum cost flow pattern.''
- Ahuja, Magnanti, Orlin, and Reddy
Este exerc�cio-programa consiste na implementa��o do algoritmo de Bellman-Ford-Moore que recebe um grafo g com comprimentos nos arcos e um v�rtice r e devolve um ciclo negativo acess�vel a partir de r ou um passeio de comprimento m�nimo de r a v, para cada v�rtice v do grafo. O comprimento len(a) de cada arco a de g � um n�mero inteiro (possivelmente negativo). Se
P=<r=v0,a1,v1,a2,v3,...,vk-1,ak,vk=v>� um passeio de um v�rtice r a um v�rtice v ent�o seu comprimento len(P) �
len(a1) + len(a2) + ... + len(ak).Assim, o comprimento de um passeio � a soma dos comprimentos do arcos no passeio; levando-se em conta o n�mero de vezes que cada arco ocorre no passeio. Um passeio P � dito (de comprimento) m�nimo se len(P) <= len(P') para todo passeio P' com a mesma ponta inicial e a mesma ponta final de P. A dist�ncia de um v�rtice r a um v�rtice v � o menor comprimento de um caminho de r a v.
O seu programa C (documento CWEB) deve chamar-se bellman.c (bellman.w, respectivamente). O programa deve utilizar a biblioteca do SGB para representa��o e recupera��o um grafo, como descrito a seguir.
Nota. A descri��o do algoritmo de Bellman-Ford-Moore que est� abaixo foi extra�da do livro:
R.E. Tarjan, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, Philadelphia, Pennysylvania, 1983.
Seja g um grafo com comprimentos nos arcos e r um v�rtice de g. Denotaremos por n e m o n�mero de v�rtices e de arcos de g.
Teorema 0. Sejam r e v v�rtices de um grafo com comprimentos nos arcos. Suponha que v � acess�vel a partir de r. Vale uma, e apenas uma, das seguintes afirma��o:
Demonstra��o. Exerc�cio.
� evidente que se v � acess�vel a partir de r, ent�o existe um caminho m�nimo de r a s. Entretanto, encontrar caminhos m�nimos � um problema computacionamente dif�cil (a menos, � claro, que n�o tenhamos pressa em encontrar o caminho). Encontrar um caminho m�nimo de r a v � t�o dif�cil quanto encontrar um caminho hamiltoniano de r a v (um problema dif�cil pra cachorro).
Felizmente (ou curiosamente) existem algoritmos eficientes para encontrar-se passeios m�nimos quando estes existem. Mais ainda, os passeios (m�nimos) encontrados pelos algoritmos s�o caminhos. Uma maneira compacta de representar passeios/caminhos m�nimos de um dado v�rtice r a todos os demais v�rtices de um grafo � atrav�s de uma certa �rvore com raiz r.
Um �rvore (ou arboresc�ncia) com raiz r � dita uma �rvore de caminhos m�nimos se todo v�rtice acess�vel a partir de r est� na �rvore e para cada v�rtice v na �rvore o caminho de r a v na �rvore � um passeio m�nimo no grafo.
Teorema 1. Seja g um grafo com comprimentos nos arcos e r um de seus v�rtices. Vale uma, e apenas uma, das seguintes afirma��o:
Demonstra��o. Exerc�cio. (Este teorema � uma das conseq��ncias da corre��o do algoritmo de Bellman-Ford-Moore.)
Se t � uma �rvore (ou arboresc�ncia) de g com raiz r e v � um v�rtice de g, ent�o definimos dist[v] como sendo o comprimento do �nico caminho de r a v na �rvore. Note que dist[v] n�o � a dist�ncia r a v no grafo, mas sim na �rvore; por esta raz�o dist[v] � muitas vezes chamdo de dist�ncia tentativa (ou candidato a dist�ncia) de r a v no grafo. Para os v�rtices que n�o est�o em t definimos dist[v] como sendo INFINITO, onde INFINITO � um n�mero suficientemente grande. Se n � o n�mero de v�rtices do grafo e L � o valor absoluto do maior comprimento de um arco ent�o, para os nossos prop�sitos, podemos considerar que INFINITO = n � L + 1. Note que para cada arco uv na �rvore vale que
dist[u] + len(uv) = dist[v].
O m�todo descrito a seguir baseia-se no teorema abaixo.
Teorema 2.
Uma �rvore com raiz r � de caminhos m�nimos
se e somente se
dist[u] == INFINITO ou dist[v] <= dist[u] + len(uv,) para cada arco uv de g,onde dist[w] � o comprimento do caminho de r a w na �rvore.
Demonstra��o. Exerc�cio. :-)
O teorema 2 pode ser usado na implementa��o de um trecho de c�digo que em tempo linear verifica se uma suposta �rvore de caminhos m�nimos � de fato uma �rvore de caminhos m�nimo Esta v�rifica��o ser� usada na implementa��o do algoritmo de Bellman-Ford-Moore, veja a se��o ``comportamento do se programa''.
EXERC�CIO : Escreva uma fun��o
int distancias_ok (Graph *g, Vertex *r){...}
que recebe um grafo g com comprimentos nos arcos
(possivelmente negativos) e um v�rtice r e devolve 1
se para cada v�rtice v o valor v->dist �
dist�ncia de r a v, em caso contr�rio a fun��o
devolve 0. O consumo de tempo de sua fun��o deve ser
linear.
O teorema 2 sugeri o seguinte m�todo iterativa, o chamado labeling method, para tentar construir uma �rvore de caminhos m�nimos com raiz r.
No in�cio de cada itera��o tem-se uma �rvore t com raiz r e
o comprimento dist[v] do caminho de r a
v na �rvore, para cada v�rtice v do grafo.
Para representar a �rvore t tem-se uma fun��o
predecessor que para cada v�rtice v fornce o v�rtice
pred[v] predecessor (ou pai) de v na
�rvore.
No in�cio da primeira itera��o pred[v] = NULL
para cada v�rtice v, dist[r] = 0 e dist[v] =
INFINITO para os demais v�rtices.
Itere o seguinte passo at�
que dist[u] + len(u,v) >= dist[v] para cada arco uv
do grafo:
LABELING STEP
(L.R. Ford).
Selecione um arco uv tal que
dist[v] > dist[u] + len(uv). Fa�a
dist[v] = dist[u] + len(u,v) e pred[v] = u.
O labeling method n�o p�ra caso o grafo contenha um ciclo negativo. Ademais, mesmo que o grafo n�o contenha ciclos negativos e o m�todo pare, ele pode demorar muito. Nosso primeiro refinamento ser� evitar que arcos sejam examinados desnecessariamente.
EXERC�CIO : Mostre um grafo com comprimentos arbitr�rios e sem ciclos negativos em que o LABELING STEP consome tempo exponecial.
O labeling and scanning method mant�m uma parti��o dos v�rtices em tr�s estados: N�O-VISTO, VISITADO e EXAMINADO. Os v�rtices no estado VISITADO ou EXAMINADO s�o exatamente aqueles que t�m `dist�ncia tentativa' finita. Inicialmente r � VISITADO e os demais v�rtices s�o N�OVISTOS. O m�todo consiste em iterar o seguinte passo at� que n�o hajam v�rtices com estado VISITADO.
SCANNING STEP. Selecione um v�rtice VISITADO u e examine-o, mudando o seu estado para EXAMINADO, atrav�s da aplica��o do labeling step a cada arco uv tal que dist[u] + len(u,v) < dist[v] e convertendo o estado de v para VISITADO (n�o importa se o estado de v era N�O-VISTO ou EXAMINADO).
O labeling and scanning method, a exemplo do labeling method, � ineficiente e n�o p�ra caso o grafo contenha um ciclo negativo acess�vel a partir de r. Entretanto, podemos transformar este m�todo em um algoritmo eficiente atrav�s de uma escolha apropriado da ordem em que os v�rtices no estado VISITADO s�o examinados, como descrito logo a seguir.
E.F. Moore e, independentemente, R.E. Bellman propuseram que os v�rtices com estado VISITADO fossem examinados de acordo com uma ordem de busca em largura (breadth-first order): entre os v�rtices com estado VISITADO examine aquele que est� nesse estado a mais tempo. Para implementar a busca em largura representamos o conjunto de v�rtices no estado VISITADO atrav�s de uma fila. Nesta implementa��o surge a quest�o do que fazer com um v�rtice no estado VISITADO que � visitado novamente. Um interpreta��o estrita de busca em largura requer que n�s movamos um tal v�rtice no estado VISITADO para o fim da fila. Entretanto, aplicaremos uma interpreta��o mais livre, deixaremos o v�rtice no estado VISITADO na sua posi��o corrente na fila. A descri��o abaixo implementa esta vers�o do labeling and scanning method usando busca em largura. Note que o m�todo, como descrito, ainda n�o p�ra se o grafo cont�m ciclos negativos.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BELLMAN-FORD-MOORE (Grafo g, V�rtice r)
para cada v�rtice v de g fa�a
estado[v] := N�O-VISTO
dist[v] := INFINITO
pred[v] := NULL
estado[r] := VISITADO
dist[r] := 0
Q := INICIALIZA-FILA(r)
enquanto Q n�o est� vazia fa�a
u := PRIMEIRO-DA-FILA(Q)
para cada uv em Adj[u] fa�a
se dist[u] + len(u,v) < dist[v] ent�o
estado[v] := VISITADO
dist[v] := dist[u]+len(u,v)
pred[v] := u
se v n�o est� em Q ent�o
INSIRA-NA-FILA(Q,v)
estado[u] := EXAMINADO
devolva dist e pred
Ao longo do algoritmo, Q � uma fila de v�rtices; essa fila � o segredo do funcionamento do algoritmo. O comando INICIALIZA-FILA(r) cria uma fila com um s� elemento, o v�rtice r. O comando PRIMEIRO-DA-FILA(Q) devolve e remove o primeiro elemento da fila Q. O comando INSIRA-NA-FILA(Q,v) insere v no fim da fila Q.
Para analisar o desempenho deste m�todo divide-se a sua execu��o em passos. O passo zero consiste do exame do v�rtice r. Para j > 0, o passo j consiste do exame de todos os v�rtices na fila ao final do passo j - 1. Cada passo pode ser executado em tempo O(n+m) pois durante cada passo cada v�rtice e cada arco � examinado no m�ximo uma vez. (Hmmm, esse O(n+m) pode ser trocado por O(m). Por qu�?) O teorema a seguir fornece um limitante superior para o n�mero total de passos.
Teorema 3. Se g � um grafo com n v�rtices,m arcos e sem ciclos negativos acess�veis a partir de r, ent�o o m�todo de BELLMAN-FORD-MOORE gasta tempo O(n+nm) e n�o mais do que n-1 passos s�o realizados.
Demonstra��o. Pode-se mostrar por indu��o em k que se existe um passeio m�nimo de r a um v�rtice v usando k arcos, ent�o no in�cio do passo k a dist�ncia tentativa dist[v] � menor ou igual ao comprimento deste passeio m�nimo.
Para transforma o m�todo de Bellman-Ford-Moore acima em um algoritmo deve-se fazer com que ele pare mesmo na presen�a de ciclos negativos. Uma maneira f�cil de fazer isto � contar o n�mero de passos executados. Inclua duas vari�veis ao m�todo, um inteiro passo e uma v�riavel �ltimo indicando o �ltimo v�rtice que foi examinado durante o presente passo do m�todo. Inicialmente passo = 0 e �ltimo = r. Depois que o v�rtice �ltimo � examinado incrementa-se de 1 a vari�vel passo e �ltimo passa a ser o �ltimo v�rtice da fila Q. Se passo recebe o valor n com a fila Q n�o vazia, o (agora) algoritmo deve parar e anunciar a presen�a de um ciclo negativo no grafo. Com este contador de passos o algoritmo gasta tempo O(n + nm) n�o importando se o grafo tem ou n�o um ciclo negativo. Usando o lema a seguir pode-se localizar um ciclo negativo, caso um tal ciclo exista. Se v � um v�rtice, ent�o
pred1[v] = pred[v]e assim por diante.
pred2[v] = pred[pred[v]]
pred3[v] = pred[pred[pred[v]]]
[...]
Lema 4. Se a fila Q n�o est� vazia no final do passo n-1 ent�o predk[v] = v para algum v�rtice v e inteiro k e o correspondente ciclo em g � negativo.
Demonstra��o. Suponha que o algoritmo � executado at� que um v�rtice w seja examinado no passo n. Defina passo[v] de um v�rtice v como sendo o m�ximo j tal que v � examinado durante o passo j. Se passo[v] � definido e positivo ent�o pred[v] e passo[pred[v]] s�o definidos e passo[pred[v]] >= passo[v] - 1. Temos que passo[w]=n. Seguindo os apontadores pred a partir de w nos devemos, em algum momento, repetir algum v�rtice, pois existem somente n v�rtices e o passo de cada v�rtice decresce de no m�ximo um em cada passo.
Uma descri��o alternativa do m�todo de Bellman-Ford-Moore, mais pr�xima de programa��o din�mica, � a que passamos a apresentar.
Defina para cada v�rtice v o valor dk(v) como sendo o menor comprimento de um passeio de r a v que possui no m�ximo k arcos, fa�a dk(v) = INFINITO se n�o existe um tal passeio.
Claramente, se n�o existe um ciclo negativo acess�vel a partir de r, a dist�ncia de r a v � igual a dn(v) (na verdade, dn-1(v)).
Algoritmicamente, a fun��o d0 � f�cil de ser computada: d0(r) = 0 e d0(v) = INFINITO se v � um v�rtice distinto de r. Em seguida, d1, d2, d3,... podem ser computadas sucessivamente atrav�s da seguinte regra:
dk+1(v) = min{dk(v), min(dk(u)+len(uv): uv arco)}para cada v�rtice v.
Este m�todo fornece a dist�ncia de r a v, para cada v�rtice v. Como vimos anteriormente n�o � dif�cil adaptar o m�doto para construir uma �rvore de caminhos m�nimo com raiz r; se o grafo n�o possui ciclo negativo � claro.
Teorema 5. Dados um grafo com comprimentos nos arcos e um v�rtice r tais que todo ciclo acess�vel a partir de r tem comprimento n�o-negativo, uma �rvore de caminhos m�nimos com raiz em r pode ser encontrada em tempo O(n2+nm).
Demonstra��o. Existem no m�ximo n itera��es e cada uma consome tempo O(n+m).
Um ciclo negativo pode ser determinado de maneira semelhante.
Teorema 6. Dados um grafo com comprimentos nos arcos e um v�rtice r, um ciclo negativo acess�vel a partir de r pode ser encontrado em tempo O(n2+nm).
Demonstra��o. Se dn != dn-1, ent�o dn(v) < dn-1(v) para algum v�rtice v. Logo, o algoritmo encontra um passei P de r a v de comprimento dn(v), que atravessa n arcos. Como P atravessa n arcos, ent�o P cont�m um ciclo C. Removendo C de P obt�m-se um passeio P' de r a v com menos do que n arcos. Assim,
len(P') >= dn-1(v) > dn(v) = len(P) = len(P') + len(C)e portanto len(C) < 0.
Tendo em vista o algoritmo de programa��o din�mica dsecrito acima pode-se facilmente implementar uma fun��o
void bellman-ford-moore (Graph *g, Vertex *r) {...}que recebe um grafo g com comprimentos arbitr�rios nos arcos e um v�rtice r e se o grafo n�o tem um ciclo negativo acess�vel a partir de r, ent�o devolve um caminho de comprimento m�nimo de r a v para cada v�rtice v do grafo. Eis a fun��o
void
bellman-ford-moore (Graph *g, Vertex *r)
{
Vertex *u0 = g->vertices;
Vertex *un = g->vertices + g->n;
long passo;
for (u = u0; u < un; u++)
{
u->dist = infinito;
u->pred = NULL;
}
r->dist = 0;
for (passo = 0; passo < n; passo++)
{
for (u = u0; u < un; u++)
{
if (u->dist != infinito)
{
Arc *a;
for (a = u->arcs; a; a = a->next)
{
Vertex *v = a=>tip;
long d = u->dist + a->len;
if (v->dist > d)
{
v->dist = d;
v->pred = u;
}
}
}
}
}
}
Este trecho de c�digo exibe a simplicidade do m�todo. O consumo de tempo da fun��o bellman-ford-moore � O(n2 + nm). Do ponto de vista de consumo de tempo assint�tico de pior caso, esta fun��o � t�o eficiente quanto a que ser� implementada neste exerc�cio-programa. Entretanto, a implementa��o sugerida para este exerc�cio-programa � mais eficiente na pr�tica.
EXERC�CIO (An�lise experimental) : Compare o consumo de tempo do seu exerc�cio-programa com o consumo de tempo da fun��o acima.
Neste exerc�cio-programa voc� implementar� o Algoritmo de Bellman-Ford-Moore para encontrar passeios m�nimos em grafos com arcos de comprimentos arbitr�rios (possivelmente negativos). Voc� pode escrever o programa em C cru ou em CWEB. Documente corretamente todas as fun��es do programa.
O programa deve receber como entrada um grafo, um v�rtices origem e um v�rtice destino e deve fornecer como sa�da um passeio m�nimo do v�rtice origem ao v�rtice destino.
O nome do seu programa dever� ser bellman e poder� ser chamado das seguintes formas (voc� pode implementar mais funcionalidades de desejar):
O seu programa deve prever pelo menos os seguintes casos, informando o fato ao usu�rio com uma mensagem conveniente:
N�o deixe de incluir algumas fun��es de auto-teste em seu programa: Se o usu�rio digitar a op��o "-teste", essas fun��es far�o testes em v�rios pontos do programa. Por exemplo, verificar�o se um suposto caminho � de fato um caminho, se uma suposta �rvore de caminhos m�nimos � de fato uma �rvore de caminhos m�nimo, etc Se a op��o "-teste" estiver ativa, � uma boa id�ia exibir a seq��ncia de v�rtices sendo examinados.
Sugest�es s�o bem-vindas!
A sa�da do seu programa deve ser enviada para a sa�da padr�o (stdout).
Os comprimentos dos passeios m�nimos encontrados devem ser fornecido, bem como o passeio do v�rtice origem ao(s) v�rtice(s) destino(s). Se o programa � chamado com os nomes dos v�rtices, os passeios m�nimos fornecidos na sa�da devem listar os nomes dos v�rtices. Caso o programa seja chamado usando os n�meros dos v�rtices, os passeios fornecidos devem listar os n�meros dos v�rtices.
Voc� pode implementar o algoritmo de Bellman-Ford-Moore como uma fun��o em seu programa, de forma a permitir que, no futuro, a mesma fun��o possa ser usada inalterada por outros programas que voc� escrever, nesta ou em outras disciplinas.
O algoritmo precisa de uma estrutura de dados auxiliar que permita as opera��es INICIALIZA-FILA, PRIMEIRO-DA-FILA, INSIRA-NA-FILA, e REMOVA-DA-FILA. A fila pode ser implementada como uma lista duplamente ligada com cabe�a de v�rtices (estruturas do tipo Vertex). Como fizemos para o algoritmo de Dijkstra.
Agora, vamos imaginar que um dia voc� queira usar, ou testar, uma outra estrutura de dados para representar est� fila, talvez mais r�pida. Levando isso em considera��o, o uso da fila em seu programa deve ser de tal forma modularizada que permita, sem necessidade de mudan�as na fun��o principal do bellman, que outra estrutura de dados substitua em seu programa as rotinas de fila que voc� escrever.
Se voc� est� em busca de inspira��o, ent�o d� uma olhada no modulo GB_DIJK (gb_dijk.w) do SGB para ver uma implementa��o do Algoritmo Dijkstra. O m�dulo MILES_SPAN (miles_span.w) cont�m uma implementa��o de uma fila atrav�s de um heap.
Copiado do arquivo gb_miles.w:
The subroutine call
The constructed graph will be ``complete''---that is, it will have edges between every pair of vertices---unless special values are given to the parameters max_distance or max_degree. If max_distance!=0, edges with more than max_distance miles will not appear; if max_degree!=0, each vertex will be limited to at most max_degree of its shortest edges.
Um exemplo de uso da fun��o miles pode ser encontrado no m�dulo MILES_SPAN (miles_span.w), como mostrado abaixo.
#include "gb_miles.h" /* the |miles| routine */
[...]
main(argc,argv)
int argc; /* the number of command-line arguments */
char *argv[]; /* an array of strings containing those arguments */
{@+unsigned long n=100; /* the desired number of vertices */
unsigned long n_weight=0; /* the |north_weight| parameter */
unsigned long w_weight=0; /* the |west_weight| parameter */
unsigned long p_weight=0; /* the |pop_weight| parameter */
unsigned long d=10; /* the |max_degree| parameter */
long s=0; /* the random number seed */
unsigned long r=1; /* the number of repetitions */
char *file_name=NULL; /* external graph to be restored */
@;
while (r--) {
if (file_name) g=restore_graph(file_name);
else g=miles(n,n_weight,w_weight,p_weight,0L,d,s);
if (g==NULL || g->n<=1) {
fprintf(stderr,"Sorry, can't create the graph! (error code %ld)\n",
panic_code); /* panic_code is set nonzero if graph
* generator panics.
* panic_code indica o problema que ocorreu,
* veja gb_graph.w
*/
return -1; /* error code 0 means the graph is too small */
}
Copiado do arquivo m�dulo GB_RAND (gb_rand.w):
This GraphBase module provides two external subroutines called random_graph and random_bigraph, which generate graphs in which the arcs or edges have been selected ``at random.'' A third subroutine, random_lengths, randomizes the lengths of the arcs of a given graph. The performance of algorithms on such graphs can fruitfully be compared to their performance on the nonrandom graphs generated by other GraphBase routines.[...]
The procedure
If dist_from or dist_to are NULL, the probability distribution is uniform over vertices; otherwise the dist parameter points to an array of n nonnegative integers that sum to 230, specifying the respective probabilities (times 230) that each given vertex will appear as the source or destination of the random arcs.
[...]
Gostaria de destacar que o uso do WEB, segundo o seu criador D. Knuth, tem as seguintes finalidades de
Mudando de assunto, um coment�rio sobre coment�rios: ``Antes de cada fun��o [e bloco] diga o que a fun��o [e bloco] faz. Procure responder as perguntas que um usu�rio faria: que dados essa fun��o recebe? que suposi��es faz sobre esses dados? que resultados devolve? N�o perca tempo tentando dizer como a fun��o faz o que ela faz.''(Paulo Feofiloff) Se o tamanho de seus blocos � razoavelmente pequeno, como deve ser, o conselho � extremamente �til.
Observa��o. C�piei o coment�rio acima da p�gina de grafos do prof. Jos� Augusto
cweave, latex,
ctangle (se voc� fez em CWEB) e gcc.
meu_prompt> make bellman.texgere o documento bellman.tex correspondente ao seu EP4,
meu_prompt> make bellman.dviproduza o Make.dvi correspondente ao seu EP4,
meu_prompt> make bellman.ccrie o arquivo bellman.c correspondente ao seu EP4, e
meu_prompt> make bellmanproduza o execut�vel de nome bellman correspondente ao seu EP4.
meu_prompt>tar -xvf ep4.tarcrie um diret�rio que tenha o seu login na rede Linux como nome. Neste diret�rio devem estar todos os arquivos do seu EP3, inclusive o Makefile que voc� usou. Se voc� achar necess�rios coloque junto um arquivo 00-leia-me, onde voc� descreve algo que achar necess�rio: como limita��es e bugs no seu programa.