MAC 328 Algoritmos em Grafos

Algoritmo de Bellman-Ford-Moore

Observação. 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 D=(V,A) um grafo e s um vértice de D. Antes de descrevermos o Algoritmo de Bellman-Ford-Moore é bom lembrarmos que nem sempre é possível encontrarmos um passeio mínimo de um vértice a todos os outros vértices de um grafo.

Teorema 1. 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:

• D possui uma árvore de caminhos mínimos com raiz s.
• D contém um ciclo negativo.

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 2. (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

O teorema acima sugeri a seguinte maneira para construirmos uma árvore de caminhos mínimos com raiz s. Para cada vértices v manteremos uma distância tentativa dist[v] de s até v e um predecssor tentativo pred[v] da árvore de caminhos mínimos. No início dist[s] = 0 e dist[v] = INFINITO para os demais vértices de D. Além disso pred[v] = NULL para todos os vértices do grafo. Iteraremos o seguinte passo até que dist[u] + len(u,v) >= dist[v]. para todo arco (u,v) de D:

LABELING STEP (L.R. Ford). Selecione um arco (u,v) tal que dist[u] + len(u,v) < dist[v] . Faça

O labeling method descrito acima 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.

O labeling and scanning method mantém uma partição dos vértices em três estados: NÃO-VISTO, ROTULADO e EXAMINADO. Os vértices ROTULADOS e EXAMINADOS são exatamente aqueles que têm distância tentativa finita. Inicialmente s é ROTULADO e os demais vértices são NÃO-VISTOS. O método consiste em repetir o seguinte passo até que não hajam vértices ROTULADOS.

SCANNING STEP. Selecione um vértice ROTULADO u e examine-o, mudando o seu estado para EXAMINADO, através da aplicação do labeling step a cada arco (u,v) tal que dist[u] + len(u,v) < dist[v] e convertendo o estado de v para ROTULADO (não importa se o estado de v era NÃO-VISTO ou EXAMINADO).

O labeling e 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 s. Entretanto, podemos transformar este método em um algoritmo eficiente através de uma escolha apropriado da ordem em que os vértices ROTULADOS serão examinados.

E.F. Moore e, independentemente, R.E. Bellman propuseram que os vértices ROTULADOS fossem examinados de acordo com uma ordem de busca em largura (breadth-first order): entre os vértices ROTULADOS examine aquele que foi rotulado a mais tempo. Para implementar a busca em largura representamos o conjunto de vértices ROTULADOS através de uma fila. Nesta implementação surge a questão do que fazer com um vértice ROTULADO que é rotulado novamente. Um interpretação estrita de busca em largura requer que nós movimentemos um vértice rotulado para o final da fila. Nos usaremos uma interpretação mais livre, deixaremos o vértice rotulado na sua posição corrente na fila. O método abaixo implementa esta versão do labeling and scanning method usando busca em largura. Note que o método, como está 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  18

BELLMAN-FORD-MOORE (Grafo D=(V,A), Vértice s)   para cada vértice v de D faça       estado[v] := NÃO-VISTO       dist[v] := INFINITO       pred[v] := NULL   estado[s] := ROTULADO   dist[s] := 0   Q := INICIALIZA-FILA(s)   enquanto Q não está vazia faça       u := PRIMEIRO-DA-FILA(Q)       para cada v em Adj[u] faça           se dist[u] + len(u,v) < dist[v] então             estado[v] := ROTULADO             dist[v] := dist[u]+len(u,v)             pred[v] := u             se v não está em Q então               INSIRA-NA-FILA(Q,v)       REMOVA-DA-FILA(Q)       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(s) cria uma fila com um só elemento igual a s. O comando PRIMEIRO-DA-FILA(Q) devolve o primeiro elemento da fila Q mas não retira esse elemento da fila. O comando INSIRA-NA-FILA(Q,v) insere v no fim da fila Q. O comando REMOVA-DA-FILA(Q) remove o primeiro elemento da fila Q.

Para analisarmos o dempenho deste método nós dividiremos a sua execução em passos. O passo zero consiste do exame do vértice s. 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(m) pois durante cada passo cada arco é examinado no máximo uma vez. O teorema a seguir fornece um limite ao número total de passos.

Teorema 3. Se D não contém um ciclo negativo acessível a partir de s então examinar os vértices através de busca em largura gasta tempo O(nm) e não mais do que n-1 passos são realizados. Caso contrário, o método não pára.

Prova. Podemos provar por indução em k que se existe um passeio mínimo de s até um vértice v usando k arcos, então no início do passo k a distância tentativa dist[v] será igual ao comprimento deste passeio mínimo.

#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 */
    }