Exemplo: algoritmo de Dijkstra

Aqui queremos achar o melhor caminho entre A e E (veja abaixo). Podemos ver que existem 6 possibilidades de caminhos entre A e E (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE) e é claro que ABDE é o melhor caminho porque seu peso é o menor. Mas nem tudo é tão simples e existem alguns casos complicados nos quais temos de usar algoritmos para encontrar o melhor caminho.
  1. Como vemos na imagem abaixo, o nó fonte (A) foi escolhido como um T-node, e seu rótulo é permanente (mostramos os nós "permanentes" com círculos cheios e T-nodes com o símbolo à).


  2. Nesta etapa, vemos que o conjunto de registros de estado de nós "tentativa" diretamente ligados ao T-node (B,C) foi alterado. Além disto, desde que B tenha menor peso, ele será escolhido como T-node e seu rótulo será mudado para permanente (veja abaixo).


  3. Nesta etapa, como na 2, o conjunto de registros de estado de nós "tentativa" diretamente ligados ao T-node (D,E) foi alterado. Além disto, desde que D tenha menor peso, ele será escolhido como T-node e seu rótulo será mudado para permanente (veja abaixo).


  4. Nesta etapa, não temos qualquer nó "tentativa", então, só identificamos o próximo T-node. Desde que E tenha o menor peso, ele será escolhido como T-node.


Chegamos ao fim. Agora temos que identificar o caminho. O nó prévio de E é D, o nó prévio de D é B e o nó prévio de B é A. Logo, o melhor caminho é ABDE. Neste caso, o peso total é 4 (1+2+1).

Apesar deste algoritmo funcionar bem, é muito complicado e toma muito tempo dos roteadores para processá-lo, com isso, a eficiência da rede diminui. Além disto, se um roteador passa uma informação errada para outros roteadores, todas as decisões dos roteadores irão se tornar ineficazes. Para entender melhor este algoritmo, aqui está o programa fonte escrito em C: 

   #define MAX_NODES 1024    
      /* máximo número de nós */
  #define INFINITY 1000000000
      /* um número maior do que todo o caminho máximo */
  int n,dist[MAX_NODES][MAX_NODES];
     /*dist[I][j] é a distância de i para j */
  void shortest_path(int s,int t,int path[ ])
  {struct state
 {
                /* o caminho em que se trabalha */
  int predecessor ;
                     /*nó prévio */
  int length
                /*comprimento da fonte até o nó*/
  enum {permanent, tentative} label
  /*estado do rótulo*/
  }state[MAX_NODES];
  int I, k, min;
    struct state *           
         p;
  for (p=andstate[0];p < andstate[n];p++)
{
       /*estado de inicialização*/
 p->predecessor=-1
 p->length=INFINITY
 p->label=tentative; 
}
state[t].length=0;
state[t].label=permanent;
   k=t;  /*k é o nó inicial */ 
    do
 {
    /* é o melhor caminho de k? */   
 for I=0; I < n; I++)
    /*este diagrama possui n nós */
  if (dist[k][I] !=0 andand state[I].label==tentative)
 {
     if (state[k].length+dist[k][I] < state[I].length)
          {
           state[I].predecessor=k;
           state[I].length=state[k].length + dist[k][I]
          }
}
 /* Encontre como tentativa o nó etiquetado com
 a menor etiqueta. */ 
   k=0;min=INFINITY;
   for (I=0;I < n;I++) 
 { 
       if(state[I].label==tentative and
      state[I].length <  min)=state[I].length;
       {
         k=I;  
       } 
   state[k].label=permanent
 }
 while (k!=s);
 /*Copie o caminho na matriz de saída*/
 I=0;k=0 
 Do{path[I++]=k;k=state[k].predecessor;
 }
  while (k > =0);
 }