"A arte de programar consiste em organizar e dominar a complexidade" - Edsger W. Dijkstra

Este artigo discute um algoritmo eficiente para o Problema de Caminho de Custo Mínimo a partir de uma origem:

Dado um digrafo com custos não-negativos nos arcos e um vértice s, encontrar um caminho de custo mínimo com raiz s no digrafo.
O algoritmo foi inventado por Dijkstra [pronuncie algo entre "Dêcstra" e "Dêicstra"] e publicado em 1959. O algoritmo pode ser usado, em particular, para encontrar um caminho de custo mínimo de um dado vértice a outro.

O algoritmo

A estrutura do algoritmo de Dijkstra é muito parecida com a do algoritmo de Prim. (Embora o algoritmo de Dijkstra, ao contrário do algoritmo de Prim, só se aplique a custos não-negativos.)

No início de cada iteração, temos uma arborescência T com raiz s. Para qualquer vértice w fora de T, o custo de w em relação a T é, por definição,

a distância de s a w no digrafo T+F,

sendo F a franja de T. Aqui, a franja de T é o conjunto de todos os arcos que saem de T. Em outras palavras, o custo de um vértice w que está fora de T é o custo de um caminho mínimo dentre os que começam em s, terminam em w, e só têm um arco — o último — fora de T. Diremos que o último arco de um tal caminho mínimo é o arco-pai de w.

Cada iteração do algoritmo de Dijkstra consiste no seguinte:

1. se a franja de T não é vazia
1.1 então seja w um vértice fora de T que tem custo mínimo
1.2 seja e o arco-pai de w
1.3 comece nova iteração com T+e no papel de T
2. senão pare

Nas implementações abaixo, a arborescência T será representada por um vetor pai. O custo de cada vértice w será armazenado em cst[w] e a ponta inicial do arco-pai de w será armazenada em fr[w].

As implementações que examinaremos abaixo têm uma peculiaridade: no início da primeira iteração, a árvore (representada pelo vetor pai) está vazia. Somente a partir do início da segunda iteração a implementação passa a se comportar de acordo com o algoritmo.

Implementação para digrafos densos

Suponha que nosso digrafo está representado por sua matriz de adjacência. Como de hábito, se v-w não é arco então G[v][w] vale maxCST. Supõe-se que o valor de maxCST é tão grande que não se confunde com o custo de um caminho simples.

/* Recebe digrafo G com custos não-negativos nos arcos e um vértice s. Calcula uma arborescência de caminhos mínimos com raiz s. A arborescência é armazenada no vetor pai. As distâncias em relação a s são armazenadas no vetor cst. */

/* A função supõe que a soma dos custos de todas os arcos é estritamente menor que maxCST.  Supõe também que o digrafo tem no máximo maxV vértices. */

void dijkstraV1(int s) { 
   int w, w0, fr[maxV];
   for (w = 0; w < n; w++) { 
      pai[w] = -1; 
      cst[w] = maxCST; 
   }
   fr[s] = s;
   cst[s] = 0.0;
   while (1) {
      double mincst = maxCST;
      for (w = 0; w < n; w++) {
         if (pai[w] == -1 && mincst > cst[w])
               mincst = cst[w0=w]; 
      if (mincst == maxCST) break;
      pai[w0] = fr[w0];
      for (w = 0; w < n; w++) 
         if (cst[w] > cst[w0] + G[w0][w]) {
            cst[w] = cst[w0] + G[w0][w]; 
            fr[w] = w0; 
         }
   }
}

Note que essa implementação é quase idêntica à implementação correspondente do algoritmo de Prim.

Duas observações técnicas:
1. Observe como a comparação de cst[w] com cst[w0] + G[w0][w] trata corretamente do caso em que w0 e w não são adjacentes e portanto G[w0][w] vale maxCST.
2. Estamos supondo, implicitamente, que maxCST é menor que a metade de DBL_MAX, de modo que a expressão cst[w0] + G[w0][w] não produz overflow.

No começo de cada iteração (a partir da segunda) temos uma arborescência com raiz s, representada pelo vetor pai. No início de cada iteração, as seguinte propriedades valem para cada vértice v:

1. se v está na arborescência então cst[v] é a distância de s a v,
senão, cst[v] é o custo do vértice v em relação à arborescência;

2. se v está fora da arborescência e cst[v] < maxCST então
fr[v] é o penúltimo vértice de um caminho simples de custo cst[v] que liga s a v.

A operação mais característica do algoritmo de Dijkstra é a relaxação de um arco:

         if (cst[w] > cst[w0] + G[w0][w]) {
             cst[w] = cst[w0] + G[w0][w]; 
         }

Essa operação aparece em toda implementação do algoritmo.

Implementação para digrafos esparsos

A implementação para digrafos representados por vetor de listas de adjacência usa uma fila de prioridades, tal como a correspondente implementação do algoritmo de Prim.

/* Recebe digrafo G com custos não-negativos nos arcos e um vértice s. Calcula uma SPT com origem s. A SPT é armazenada no vetor pai. As distâncias em relação a s são armazenadas no vetor cst. */

/* A implementação supõe que a soma dos custos de todos os arcos é estritamente menor que maxCST.  Supõe também que o digrafo tem no máximo maxV vértices. */

void dijkstraEsparso (int s) { 
   int w, w0, fr[maxV], p;
   PQinit(); 
   for (w = 0; w < n; w++) 
      pai[w] = fr[w] = -1; 
   fr[s] = s; 
   cst[s] = 0.0; 
   PQinsert(s);
   while (!PQempty()) {
      w0 = PQdelmin(); 
      pai[w0] = fr[w0]; 
      for (p = 0; p < grau[w0]; p++) {
         w = G[w0][p].w;
         if (fr[w] == -1) { 
            cst[w] = cst[w0] + G[w0][p].cst; 
            PQinsert(w); 
            fr[w] = w0; 
         } 
         else if (cst[w] > cst[w0] + G[w0][p].cst) {
            cst[w] = cst[w0] + G[w0][p].cst; 
            PQdec(w); 
            fr[w] = w0; 
         }
      }
   }
}

(Note a operação de relaxação if (cst[w] > cst[w0]+G[w0][p].cst) { cst[w] = cst[w0]+G[w0][p].cst; } característica do algoritmo de Dijkstra.)

A função dijkstraEsparso usa uma fila de vértices com prioridades definidas pelo vetor cst. A fila é manipulada pelas seguintes funções:

PQinit(): inicializa uma fila de vértices em que todo vértice v tem prioridade cst[v].
PQempty(): devolve 1 se a fila estiver vazia e 0 em caso contrário.
PQinsert(v): insere o vértice v na fila.
PQdelmin(): retira da fila um vértice de prioridade mínima.
PQdec(v): reorganiza a fila depois que o valor de cst[v] foi decrementado.
A implementação clássica da fila de prioridades usa uma estrutura de heap.

Tal como fizemos com o algoritmo de Prim, podemos organizar a implementação do algoritmo de Dijkstra de maneira um pouco diferente, inserindo todos os vértices na fila de prioridades antes mesmo do início do processo iterativo:

void dijkstraV2 (int s) { 
   int w, w0, p;
   PQinit(); 
   for (w = 0; w < n; w++) { 
      pai[w] = -1; 
      cst[w] = maxCST; 
      PQinsert(w); 
   }
   pai[s] = s;
   cst[s] = 0.0; 
   PQdec(s);
   while (!PQempty()) {
      w0 = PQdelmin();
      if (cst[w0] == maxCST) break;
      for (p = 0; p < grau[w0]; p++) {
         w = p->w;
         if (cst[w] > cst[w0] + G[w0][p].cst) { 
            cst[w] = cst[w0] + G[w0][p].cst; 
            PQdec(w); 
            pai[w] = w0; 
         }
      }
   }
}

Fonte: IME