Avaliação do Usuário

Estrela ativaEstrela ativaEstrela ativaEstrela ativaEstrela inativa
 


IMPLEMENTAÇÃO DO ALGORITMO


A implementação do algoritmo para cálculo do caminho mais curto em uma rede está representada abaixo na linguagem simbólica de programação, mais conhecida como "Portugol".

Programa Dijkstra;

/*Conjunto S: Lista encadeada de inteiros, contendo os nós
da rede exceto o nó origem, implementado através de uma classe*/
Tipo Conjunto {

  /*Variável que indica o nó atual, para o qual o
  cursor da lista está apontando*/
  noAtual: inteiro
  
  /*Variável que indica a quantidade de nós atualmente
  existentes no conjunto*/
  qtdNos: inteiro
  
  /*Função que inclui um nó no conjunto*/
  Função incluir(u: inteiro): booleano
  
     /*Código que implementa a função... */
  
  Fim Função
  
  /*Função que retira um nó do conjunto*/
  Função retirar(u: inteiro): booleano
  
    /*Código que implementa a função... */
  
  Fim Função
  
  /*Função que aponta para o primeiro nó e retorna seu número */
  Função primeiro(): inteiro
  
    /*Código que implementa a função... */
  
  Fim Função
  
  /*Função que aponta para o último nó e retorna seu número */
  Função ultimo(): inteiro
  
    /*Código que implementa a função... */
  
  Fim Função
  
  /*Função que aponta para o próximo na, a partir do atual,
  e retorna seu número */
  Função próximo(): inteiro
  
    /*Código que implementa a função... */
  
  Fim Função
  
  /*Função que indica se um nó existe no conjunto */
  Função existe(u: inteiro): booleano
  
    /*Código que implementa a função... */
  
  Fim Função

}

Variáveis

  /*Contadores auxiliares para loop.*/
  i, j: inteiro;
  
  /*Valor que representa infinito. Soma de todas as arestas mais 1.*/
  infinito: inteiro;
  
  /*Número de nós da rede. Informado pelo usuário.*/
  n: inteiro;
  
  /*Distância desde a origem até o nó u, apagado, somada com
  o peso da aresta   de u até v, o seu vizinho, cuja distância
  está sendo atualmente calculada.*/
  C: inteiro;
  
  /*Nó de origem. Informado pelo usuário.*/
  origem: inteiro;
  
  /*Nó mais próximo da origem, ainda presente no conjunto S.*/
  maisProximo: inteiro;
  
  /*Lista encadeada do tipo Conjunto, contendo os nós
  da rede, exceto o nó origem.*/
  S: Conjunto;
  
  /*Matriz contendo o custo entre cada par de nós.*/
  Custo[][]: vetor bidimensional de inteiros;
  
  /*Matriz contendo o próximo hop para cada nó.*/
  R[]: vetor unidimensional de inteiros;
  
  /*Matriz contendo a distância para cada nó. */
  D[]: vetor unidimensional de inteiros;


/*Retorna o nó que ainda se encontra em S e que possui o menor
custo desde a origem, ou zero caso não existam mais nós.*/
Função mínimo(): inteiro ;

  /*Variável que guarda o número do nó do conjunto S,
  cuja distância seja a mínima atualmente.*/
  minimoAtual: inteiro;
  
  /*Variável que guarda o número do próximo nó do
  conjunto S, para comparação com o mínimoAtual*/
  proximoNo: inteiro;
  
  /*Inicializando o mínimoAtual com o primeiro
  do conjunto S*/
  minimoAtual ← S.primeiro;
  
  /*Inicializando o proximoNo com o próximo nó
  do conjunto S*/
  proximoNo ← S.proximo;

  Repita
  
    /*Comparando o próximo e o atual*/
    Se D[proximoNo] ‹ D[minimoAtual] então
    
      /*Atualizando o mínimo atual*/
      minimoAtual ← proximoNo
    
    Fim Se
    
    /*Buscando o próximo nó*/
    proximoNo ← S.proximo
  
  /*Terminando o loop quando não houver mais nós*/
  Até proximoNo = 0

Fim Função

/*Início da execução do programa.*/
Início

  /*Usuário informa o número de nós da rede*/
  Leia n;
  
  /*Usuário informa o nó de origem*/
  Leia origem;
  
  /*Usuário informa o valor que representa o infinito.
  Deve ser maior que o maior caminho do grafo*/
  Leia infinito:
  
  /*Loop para inicialização da matriz de custo*/
  Para i de 1 até n
  
    Para j de 1 até n
      /*Usuário informa o custo entre cada par de nós*/
      Leia Custo[i][j];
    Fim Para
  
  Fim Para
  
  /*Loop para inicialização do conjunto S*/
  Para i de 1 até n
  
    Se i origem então
      /*Caso o nó não seja a origem será incluído em S*/
      S.incluir(i);
    Fim Se
  
  Fim Para
  
  /*Loop para inicialização da matriz de distâncias
  a partir da origem*/
  Para i de 1 até n
  
    /*Distância até o nó i recebe o custo entre a
    origem e i*/
    D[i] ← Custo[origem][i]
  
  Fim Para
  
  /*Loop para inicialização da matriz de roteamento*/
  Para i de 1 até n
  
    /*Caso haja uma aresta entre origem e o nó i o próximo hop
    para i recebe i. Caso contrário recebe 0*/
    Se Custo[origem][i] > 0 e Custo[origem][i] ‹ infinito então
      R[i] ← i
    Senão
      R[i] ← 0
    Fim Se
  
  Fim Para
      
  /*Início do cálculo da rota mínima*/
  Repita
  
    /*A variável maisProximo recebe o nó que está no conjunto S,
    cuja distância seja a menor*/
    maisProximo ← mínimo()
    
    /*Caso ainda haja nós em S, maisProximo será diferente de 0*/
    Se maisProximo > 0 então
    
      /*Caso o custo do maisProximo seja infinito não há mais arestas
      a partir da origem até os nós restantes*/
      Se D[maisProximo] = infinito então
      
        Msg: “Não há mais sucessores da origem em S!”;
        /*Fim do cálculo*/
        Fim;
      
      Fim Se
    
      /*Agora vamos retirar do encadeamento o nó escolhido, caso ele não
      seja infinito, pois se chegou até aqui é porque ainda há nós em S*/
      S.retirar(maisProximo);
    
      Para i de 1 até n
      
        /*Caso exista uma aresta entre o maisProximo e algum nó, este nó é
        vizinho dele então a distância será verificada. Para saber se há
        uma aresta basta saber se o custo é maior que 0 e menor que infinito*/
        Se Custo[maisProximo][i] > 0 e Custo[maisProximo][i] ‹ infinito então
        
          /*Caso o vizinho ainda esteja em S será calculada a distância*/
          Se S.existe(i) então
          
            /*A variável temporária C recebe o custo até o vizinho*/
            C ← D[maisProximo] + Custo[maisProximo][i]
          
            /*Se for menor que o custo atual do vizinho, atualiza os dados*/
            Se C ‹ D[i] então
            
              /*Próximo hop para i, o vizinho do maisProximo, recebe
              o mesmo hop do maisProximo*/
              R[i] ← R[maisProximo]
              
              /*Distância mínima da origem até o nó i recebe o valor de C */
              D [i] ← C
            
            Fim Se
          
          Fim Se
        
        Fim Se
      
      Fim Para
    
    Fim Se
  
  Até maisProximo = 0

  /*Apresentação do Resultado*/
  /*Título do relatório*/
  /*Faça os ajustes de espaço para linguagem que utilizar*/
  Escreva “Nó        Distância da Origem    Próximo Hop” + [quebra de linha]
  Para i de 1 até n
     *Distância e próximo hop para cada nó, a partir da origem*/
    Escreva i + “:   ” + D[i] + “              ” + R[i] + [quebra de linha]
  Fim Para

Fim Programa

Espero que tenham gostado.

Obrigado e até o próximo artigo...

 

{jcomments on}

Seja social. Compartilhe!