Avaliação do Usuário

Estrela ativaEstrela ativaEstrela ativaEstrela ativaEstrela inativa
 


INTRODUÇÃO

O algoritmo de Dijkstra é utilizado para se calcular o caminho mais curto em um grafo. Para isso deve ser informada a matriz de custo da rede, o nó origem, a partir do qual as distâncias serão calculadas, e um valor que represente o infinito, ou seja, o custo da aresta entre dois nós que não tem ligação.

Para o cálculo de caminho mais curto em redes de computadores é utilizada uma versão ligeiramente modificada do algoritmo, na qual será mantido um conjunto com todos os nós da rede, exceto o nó origem. Conforme seja calculada a distância mínima para um nó, este será retirado do conjunto, e assim por diante.

 

PROGRAMA

Esta implementação do algoritmo oferece a possibilidade de se utilizar uma rede qualquer, com o custo de cada aresta sendo informado pelo usuário, ou verificar o funcionamento a partir do exemplo dado, descrito adiante.

Ao final da execução o resultado dos cálculos é apresentado, no qual são exibidos a distância mínima, o próximo hop e a pista para cada nó, a partir da origem.

 
REDE DE EXEMPLO

Exemplo de nós de rede (grafo/djikstra)

  • 1 – Origem
  • 2, 3, 4 e 5 – Nós que tem ligação com a origem
  • 6 a 22 – Nós que não tem ligação com a origem
  • infinito – 500 (Valor superior à soma de todas as arestas, convencionado, representando o valor infinito, que é a distância entre dois nós que não possuem ligação. Em uma rede sem limites poderia ser por exemplo nulo, ou algo que não pudesse ser considerado um valor válido)

Estruturas de dados necessárias para a implementação:

 

Vetor Custo[i][j]: inteiro

Armazena o custo da distância entre os nós i e j. Caso i e j sejam o mesmo vértice o custo será zero. Caso não haja aresta entre os dois nós o custo será infinito (infinito vale 500, conforme convencionado).

            Ex:      Custo[2][10] = custo da distância entre os nós 2 e 10 = 7;

                        Custo[15][18] = custo da distância entre os nós 15 e 18 = 5;

                        Custo[19][19] = custo da distância entre os nós 19 e 19 = 0;

                        Custo[6][17] = custo da distância entre os nós 6 e 17 = 500 (infinito);

 

Vetor D[i]: inteiro

Armazena a distância corrente da origem até o nó i.

            Ex:      D[2] = distância (ou peso) da origem até o nó 2 = 4;

                        D[5] = distância (ou peso) da origem até o nó 5 = 12;

 

Vetor R[i]: inteiro

Armazena o número do nó que é o próximo hop para o nó i, a partir da origem. Deve ser um dos nós de 1 a 4, pois são os únicos que tem ligação com a origem.

            Ex:      R[2] = próximo hop da origem para o nó 2 = 2;

                        R[3] = próximo hop da origem para o nó 3 = 3;

                        R[8] = próximo hop da origem para o nó 8 = 4;

 

Conjunto S: Lista encadeada de inteiros

Armazena cada nó exceto o nó da origem. Pode ser implementado utilizando-se ponteiros duplamente encadeados para que seja possível a retirada de um nó ou o passeio pelos nós do conjunto. O conjunto deve prover funções de inclusão, retirada e pesquisa de nós.


Funções de S:

           

  • incluir(u: inteiro): booleano - inclui um nó no conjunto. O número do nó a ser incluído deve ser passado como argumento para a função;
  • retirar(u: inteiro): booleano - retira um nó do conjunto. O número do nó a ser retirado deve ser passado como argumento para a função;
  • primeiro(): inteiro - move o cursor para o primeiro nó do conjunto, retornando o seu número, ou zero caso não haja nenhum nó no conjunto;
  • ultimo(): inteiro - move o cursor para o último nó do conjunto, retornando o seu número, ou zero caso não haja nenhum nó no conjunto;
  • proximo(): inteiro - move o cursor para o próximo nó, a partir da posição atual do cursor, retornando o seu número, ou zero caso não haja mais nenhum nó no conjunto;
  • existe(u: inteiro): booleano – indica se um nó existe atualmente no conjunto, retornando verdadeiro em caso afirmativo, ou falso caso contrário.

 

Variável C: inteiro

Armazena temporariamente o valor da distância entre a origem e um nó qualquer, somado com o peso da aresta entre o nó e um vizinho seu. É utilizado para a comparação entre a distância encontrada atualmente e a distância armazenada no vetor D(i).

 

Variável Origem: inteiro

Armazena o número do nó de origem. Deve ser informado pelo usuário no início do programa.

 

Variável MaisProximo: inteiro

Utilizada para guardar temporariamente o número do nó que ainda esteja no conjunto S e que é atualmente o mais próximo da origem. O mais próximo é o nó que será apagado para que sejam calculadas as distâncias até os seus vizinhos.

 

Seja social. Compartilhe!