Algoritmo de Dijkstra C ++

O algoritmo de Dijkstra também é conhecido como o mais curto algoritmo de caminho possível. É o procedimento encontrar o caminho mais curto entre os nós/ bordas do gráfico. O gráfico mais curto de uma árvore é criado começando do vértice da fonte para todos os outros pontos do gráfico.

Algoritmo

• Antes da implementação direta do gráfico Dijkstra na linguagem de programação C ++, precisamos entender o funcionamento deste algoritmo de gráfico.
• O primeiro passo é a criação de "sptset", que é abreviado como o conjunto de árvores de caminho mais curto; Ele armazena o registro daqueles vértices incluídos no caminho mais curto. Na fase inicial, este conjunto é declarado como nulo.
• Na próxima etapa, primeiro, todos esses valores nos nós são declarados como infinitos, pois não sabemos o peso dos caminhos até agora.
• Escolha um vértice "u" que ainda não está presente no spttset e tem valor mínimo. Em seguida, inclua -o no sptset. Depois disso, atualize os valores de distância de todos os nós que são vértices adjacentes de “U.”Tudo isso é feito sob o loop até que o SPTSET possa conter todos os vértices.

Implementação do algoritmo de gráfico de Dijkstra

Aqui está a implementação do gráfico Dijkstra, onde um programa é escrito para a representação da matriz de adjacência desse gráfico. Inicie o programa adicionando duas bibliotecas muito essenciais para a realização do programa na linguagem de programação C ++, que nos torna capazes de usar os recursos CIN e Cout.

#incluir
#incluir

Depois de descrever as bibliotecas, agora forneceremos o tamanho ou vértices do gráfico em que precisamos do caminho mais curto. Damos 9 vértices, o que significa que a matriz é um quadrado de [9] [9].

#Define v 9

"V" é para os vértices. Como o algoritmo requer muitas etapas para realizar a tarefa fornecida, cada etapa ou processo é dividida em funções separadas para executá -las para que o código seja claro e não haja ambiguidade em relação à lógica. Além disso, a complexidade também é removida.

A função é criada aqui para pesquisar o vértice que possui um valor de distância mínimo; Ele contém o conjunto de vértices que não estão incluídos na árvore com o caminho mais curto. A função conterá a matriz de distância e um sptsset do tipo bool, o conjunto de árvores de caminho mais curto e a matriz como um parâmetro da função. Dentro da função, o valor mínimo é inicializado declarando uma variável de tipo inteiro que armazenará o valor retornado. Duas variáveis, Max e o min_index são introduzidas.

Int min = int_max, min_index;

A for loop é usado aqui; em que um vértice inicial em todos os vértices é tomado, o loop continuará até que todos os vértices sejam atravessados. Uma condição é aplicada aqui usando uma declaração IF que verifica se o conjunto de caminho mais curto é falso meios, está vazio agora e a distância do vértice é menor que a do valor mínimo do vértice, que é declarado anteriormente, Em seguida, aloque o valor atual do vértice como min, e o min_index também conterá o mesmo valor do vértice.

Min = dist [v], min_index = v;

Depois que o valor mínimo do vértice é calculado, o próximo é o processo de criação de uma função que exibirá a matriz de distância que foi construída anteriormente. Um loop irá iterar cada índice que será acessado e exibido. Primeiro, o número do vértice é exibido a partir do valor zero, e a distância do vértice da fonte também é mencionada aqui com uma sequência. Esta função é declarada aqui, mas será chamada mais adiante no programa, quando todo o caminho for calculado como a menor distância.

A parte principal de todo o código-fonte é declarada agora, onde a implementação do caminho mais curto de fonte única é calculada. Um gráfico será representado pela representação da matriz de adjacência. Esta função levará uma matriz gráfica e a fonte como valores de parâmetros que atuarão como entrada para o cálculo da distância. Primeiro, dentro da função, declararemos a matriz de saída que conterá o caminho mais curto da fonte para um ponto específico. Em segundo lugar, é declarada uma matriz variável booleana, o que retornará verdadeiro se o vértice for incluído na determinação do caminho mais curto no início.

Int dist [v]; SPTSET BOOL [V];

Todas as distâncias serão definidas como infinitas, e a matriz de caminho mais curta é falsa. Com a ajuda de um loop, todo esse processo ocorrerá.

Dentro do loop, o vértice de distância mínima é escolhido no conjunto de vértices que ainda não foram processados. Na primeira iteração, 'u' é sempre igual ao vértice da fonte.

Int u = Mindistância (Dist, sptset);

Os vértices escolhidos e percorridos são colhidos e marcados como processados ​​ao definir a variável booleana é verdadeira.

sptset [u] = true;

Quando um vértice é adicionado, todos os vértices adjacentes a esse vértice em particular também são verificados; Isso precisa de uma atualização. Portanto, atualizaremos o valor de "distiço" dos vértices adjacentes daqueles vértices que foram piquetes até agora.

Dentro disso, para o loop, atualizaremos dist [v] se e somente se não estiver no sptset, existe uma linha chamada uma vantagem do vértice u a V, e o peso total do caminho que começa a partir de "src" Para "V", passando por "U" é menor que o valor atual presente no disto [v].

Dist [v] = dist [u] + gráfico [u] [v];

Depois disso, a função de impressão que declaramos acima é chamada passando a matriz dist [] como um parâmetro.

PrintSolution (Dist);

No programa principal, criamos um gráfico de 9*9 matrizes. E então, a função chama a função Dijkstra é feita, através da qual o gráfico é passado.

Salve o código inteiro. Compilar o código usando um compilador G ++ no terminal Ubuntu. '-o' é um símbolo que salva a saída do arquivo.

$ g ++ -o dij dij.c
$ ./dij

Você pode ver que todos os vértices em cada linha separada são exibidos junto com a distância de cada vértice da fonte.

Este código ajuda a calcular a menor distância, mas não suporta calcular as informações sobre o caminho. Esse código -fonte é bom para os gráficos não direcionados, mas pode ser possível usar para os gráficos direcionados também. Ao usar este código, podemos encontrar a menor distância do ponto de fonte para todos os outros vértices no gráfico.

A complexidade do tempo do gráfico Dijkstra

Falaremos sobre a complexidade do tempo da implementação. Isso é:

0 (v^2).

Isso pode ser reduzido para 0 (e log V) usando o processo de heap binário. O gráfico Dijkstra não é para os gráficos que têm pesos negativos.

Conclusão

Este artigo contém o processo de encontrar a distância mais curta entre o nó de origem e o restante dos nós. Pode haver muitas abordagens para isso. Mas o gráfico Dijkstra é um dos melhores mecanismos para esse fim. Ele foi projetado para gráficos não direcionados. Explicamos o processo passo a passo com o código -fonte para torná -lo vívido para os novos usuários. Esperamos que esse esforço esteja à altura dos leitores.