Algoritmo de Dijsktra: C++, Python Exemplo de Código
Sarah Chen
Qual é o caminho mais curto ou a distância mais curta?
Um caminho do vértice de origem ao vértice de destino que custa um mínimo é o caminho mais curto ou a distância mais curta. Na teoria dos grafos, é possível ter múltiplas rotas de uma origem a um destino. Entre essas rotas, se houver uma rota que custe um valor mínimo, podemos chamá-la de algoritmo de caminho mais curto.
Aqui, “Custo” significa o número de nós na rota ou a soma dos custos em cada caminho. Um caminho pode ter uma ou várias arestas. A conexão entre dois vértices é chamada de “aresta”. Existem vários tipos de algoritmos de caminho mais curto, como algoritmo de Dijkstra, algoritmo de Bellman-Ford, etc.
Aqui, discutimos sobre o Algoritmo de Dijkstra
Vejamos o seguinte gráfico ponderado:
- O termo “Ponderado” significa mover custos de um nó para outro. Por exemplo, passando do nó 1 para o nó 2, o custo ou peso é 1.
- O caminho entre o nó 1 e o nó 2 é chamado de aresta.
- “Não direcionado” significa que você pode mover um nó para outro e voltar ao nó anterior. Então, se tentarmos encontrar todas as rotas do nó 1 ao nó 7, então será:
| Rota ou Caminho | Custo |
|---|---|
| 1-2-6-7 | (1+3+3) = 7 |
| 1-2-3-7 | (1+9+1) = 11 |
| 1-3-7 | (7+1) = 8 |
| 1-4-5-7 | (6+2+5) = 13 |
Dentre essas quatro rotas, podemos perceber que a primeira rota nos custará 7. Portanto, é o caminho mais curto em termos de custo.
Como funciona o algoritmo de Dijkstra
O algoritmo Dijkstra pode encontrar a distância mais curta em gráficos ponderados direcionados e não direcionados. Este algoritmo é ganancioso porque sempre escolhe o nó mais curto ou mais próximo da origem. O termo “ganancioso” significa que entre um conjunto de resultados ou resultados, o Algoritmo escolherá o melhor deles.
Aqui, tentamos encontrar os caminhos mais curtos entre todas as outras rotas. Assim, o Algoritmo de Dijkstra encontra todos os caminhos mais curtos a partir de um único nó de destino. Como resultado, ele se comporta como um algoritmo ganancioso.
Na seção “exemplo” abaixo, você verá a abordagem passo a passo. Funciona da seguinte maneira:
Passo 1) Inicialize o nó inicial com custo 0 e o restante do nó como custo infinito.
Passo 2) Mantenha uma matriz ou lista para acompanhar os nós visitados
Passo 3) Atualize o custo do nó com o custo mínimo. Isso pode ser feito comparando o custo atual com o custo do caminho. (A demonstração é mostrada na seção de exemplo)
Passo 4) Continue a etapa 3 até que todos os nós sejam visitados.
Depois de concluir todas essas etapas, encontraremos o caminho que custa o mínimo da origem ao destino.
Diferença entre Dijkstra e BFS, DFS
A principal diferença entre Dijkstra e BFS-DFS é que Dijkstra é o algoritmo de localização de caminho mais curto e BFS, DFS é o algoritmo de localização de caminho. Em casos gerais, o BFS e o DFS não consideram o custo ao encontrar o caminho. Portanto, esses algoritmos não podem garantir o caminho mais curto.
Demonstração em grade 2D de como o BFS funciona
Esta demonstração indica que o BFS apenas encontra o caminho. Porém, não se importa com o peso do caminho. BFS (Pesquisa em amplitude) assume que viajar de um nó para outro custará apenas 1.
Mas vejamos um gráfico de exemplo:
Aqui ele encontra um caminho no nível 2. O BFS percorre o gráfico em ordem de nível. Então, ele viaja como:
Passo 1) Comece no nó “1” e visite todos os nós adjacentes 2,3,4
Passo 2) Marque o nó 2,3,4 como nível 1 e visite seus nós adjacentes. Ele continuará explorando todos os nós adjacentes até chegar ao nó de destino.
Em termos de DFS, ele percorrerá o caminho de 1 a 7 da seguinte forma:
- 1→2→3→7 (custo original 10, custo DFS 3)
- 1→2→6→7 (custo original 7, custo DFS 3)
- 1→3→7 (custo original 8, custo DFS 2)
- 1→4→5→7 (custo original 13, custo DFS 3)
Como podemos ver, o DFS calcula seu custo de caminho com o número de profundidade ou número de arestas.
O DFS faz o seguinte:
- O DFS pode encontrar um caminho da origem (vértice inicial) até o destino.
- Ele não pode garantir se o caminho descoberto do nó de origem ao destino é o caminho mais curto ou não.
Porém, em termos do Algoritmo Dijkstra, ele escolherá arestas com base em seu custo. Como um algoritmo ganancioso, ele escolherá os caminhos de custo melhor ou mínimo.
Exemplo de algoritmo de Dijkstra
O Algoritmo de Dijkstra usa o custo ou peso para calcular o custo total do caminho.
O objetivo do Algoritmo de Dijkstra é minimizar esse custo ou peso total. No exemplo mostrado acima, encontramos os melhores caminhos do nó 1 ao nó 7 e, em seguida, calculamos todos os custos.
No Algoritmo de Dijkstra, ele encontrará os caminhos mais curtos calculando os pesos. Não procurará todos os caminhos possíveis. Vamos demonstrar o Algoritmo de Dijkstra com um exemplo. Por exemplo, você foi solicitado a encontrar o caminho mais curto do nó 1 ao 7.
Para este processo, as etapas são fornecidas abaixo:
Passo 1) Inicialize o custo do nó inicial como 0.
Resto do nó, atribua “Inf”. Isso significa que não existe nenhum caminho entre o vértice inicial (a origem) e o nó, ou o caminho ainda não foi visitado.
Passo 2) Ao selecionar o nó 1, ele será marcado como visitado. Em seguida, atualize todos os vizinhos adjacentes do nó 1. 2,3,4 são os nós vizinhos do nó 1.
Ao atualizar um custo, precisamos seguir o procedimento abaixo:
Podemos atualizar o custo de cada nó usando a fórmula acima. Por exemplo, estávamos no nó 1 e precisávamos atualizar o custo do nó adjacente 2,3,4.
Após a atualização, o custo ou peso ficará assim:
Etapa 3) Para o nó “2”, os vizinhos são 6 e 3. Estamos atualizando o custo em “6” comparando o infinito (valor atual). O custo do nó 2 + custo do caminho de 2 a 6. Simplesmente dizendo, o nó “6” terá o custo de 1+3 ou 4.
O nó 3 é vizinho do nó 2. Porém, calculamos seu custo na etapa anterior, que foi 7. Agora, se nosso caminho for 1-2-3, o nó 3 terá um custo de 10. Caminho 1-2- 3 custará 10, enquanto 1 a 3 custará 7.
Etapa 4) Para o nó 3, o nó vizinho é 7. Portanto, comparando o valor atual do nó 7 com o custo do caminho (7+1) ou 8, atualizaremos o custo do nó 7. Isso é 8.
Então, encontramos um caminho do nó 1 ao nó 7, e é 1→ 3→ 7. O custo é 8.
Etapa 5) Para o nó 4, atualizaremos o custo do nó adjacente de acordo. Portanto, o nó “5” terá um custo atualizado de 8. Após a etapa 4,5, ficará assim:
Agora, o caminho 1-3-7 tem o custo de 8 (anteriormente). O nó “7” não foi marcado como visitado porque podemos chegar ao nó “7” a partir do nó “6”. O caminho “1-2-6” teve um custo de 4. Portanto o caminho 1-2-6-7 terá o custo de 7.
Como 7 <8, é por isso que o caminho mais curto do vértice de origem “1” ao vértice de destino “7” será 1-2-6-7 e o custo será 7. Anteriormente era 1-3-7 e o custo tinha 8 anos.
Então, o gráfico final ficará assim:
A aresta marcada com uma linha preta é o nosso caminho mais curto de 1 a 7 e nos custará 7.
Algoritmo de Pseudo Código Dijkstra
Aqui está o pseudocódigo do algoritmo de Dijkstra
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ implementação Algoritmo de Dijkstra
Para implementar o algoritmo de Dijkstra usando C++, aqui está o código:
#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
int min = INT_MAX;
int min_index = INT_MAX;
for (int i = 0; i < size; i++) {
if (!visited[i] & amp; & distance[i] <= min) {
min = distance[i];
min_index = i;
}
}
return min_index;
}
void printParentPath(int parent[], int i) {
if (parent[i] == -1) {
return;
}
printParentPath(parent, parent[i]);
cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
int distance[size];
bool visited[size];
int parent[size];
for (int i = 0; i < size; i++) {
parent[0] = -1;
distance[i] = INT_MAX;
visited[i] = false;
}
distance[source] = 0;
for (int i = 0; i < size - 1; i++) {
int U = minimumDistance(distance, visited);
visited[U] = true;
for (int j = 0; j < size; j++) {
int curr_distance = distance[U] + graph[U][j];
if (!visited[j] & amp; & graph[U][j] & amp; &
curr_distance < distance[j]) {
parent[j] = U;
distance[j] = curr_distance;
}
}
}
cout << "Vertex\t\tDistance\tPath" << endl;
for (int i = 1; i < size; i++) {
cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
<< source + 1 << " ";
printParentPath(parent, i);
cout << endl;
}
}
int main() {
int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
{7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
{0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 5, 3, 0}};
dijkstra(graph, 0);
}
Saída:
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python implementação Algoritmo de Dijkstra
Para implementar o algoritmo de Dijkstra usando python, aqui está o código:
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = 1e11
min_index = 1e11
for i in range(num_of_vertex):
if not visited[i] and distance[i] & lt; = _min:
_min = distance[i]
min_index = i
return min_index
def printParentNode(parent, i):
if parent[i] == -1:
return
printParentNode(parent, parent[i])
print("{} ".format(i + 1), end = "")
def dijkstra(graph, src):
distance = list()
visited = list()
parent = list()
for i in range(num_of_vertex):
parent.append(-1)
distance.append(1e11)
visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
visited[U] = True
for j in range(num_of_vertex):
curr_distance = distance[U] + graph[U][j]
if not visited[j] and graph[U][j] and curr_distance & lt;
distance[j]: parent[j] = U
distance[j] = curr_distance
print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex):
print("{}->{}\t\t{}\t\t{}
".format(src + 1, i + 1, distance[i], src + 1), end = "")
printParentNode(parent, i)
print("")
graph = [
[0, 1, 7, 6, 0, 0, 0],
[1, 0, 9, 0, 0, 3, 0],
[7, 9, 0, 0, 0, 0, 1],
[6, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 3, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)
Saída:
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Podemos ver que o Algoritmo calcula a distância mais curta do nó de origem.
Aplicação do Algoritmo Dijkstra
O Dijkstra Algo tem um grande conjunto de utilizações. Entre eles, é amplamente utilizado na área de redes. Aqui estão alguns dos usos do algoritmo de Dijkstra na vida real:
Dijkstra no mapa do Google: Basicamente, este algoritmo é a espinha dorsal para encontrar os caminhos mais curtos. Como podemos ver na saída do trecho de código acima.
O Google não usa o algoritmo Dijkstra simples. Em vez disso, ele usa uma versão modificada. Quando você seleciona um destino, vários caminhos são exibidos no Google Map. Dentre esses caminhos, alguns caminhos são separados para o usuário. Esses caminhos selecionados são baseados no “tempo”. Portanto, “tempo” é um custo extremo para o caminho mais curto.
Dijkstra em roteamento IP: Roteamento IP é uma terminologia de rede. Significa como seu pacote de dados está sendo enviado ao receptor por diferentes caminhos. Esses caminhos consistem em roteadores, servidores, etc. No roteamento IP, existem diferentes tipos de protocolos.
Esses protocolos ajudam o roteador a encontrar os caminhos mais curtos para enviar os dados. Um dos nomes do protocolo é “OSPF (Open Shortest Path First)”. OSPF usa algoritmo dijkstra. O roteador mantém uma tabela de rotas. Cada roteador compartilha sua tabela com roteadores vizinhos. Após receber a tabela atualizada, eles deverão calcular novamente todos os caminhos. Nesse momento, o roteador usa o algoritmo Dijkstra.
Limitação do Algoritmo de Dijkstra
O algoritmo de Dijkstra não pode garantir o caminho mais curto no gráfico de aresta negativa. O algoritmo Dijkstra segue estas metodologias:
- Um caminho mais curto será percorrido de um nó para outro.
- Uma vez selecionado o caminho mais curto entre dois nós, ele não será calculado novamente.
Aqui, observe dois exemplos com arestas negativas.
No gráfico esquerdo, existem três vértices. Dijkstra será executado no gráfico da seguinte forma:
Passo 1) O vértice inicial “1” será inicializado em zero. Os outros nós terão infinito.
Passo 2) Marque o nó “1” como visitado e inclua-o no caminho mais curto.
Passo 3) A distância do nó de origem 1 aos nós “2” e “3” é definida como infinito, pois o caminho mais curto ainda não foi calculado. Assim, qualquer caminho que custe menos que o infinito será adicionado ao caminho mais curto (abordagem gananciosa).
Passo 4) Atualizando a distância do vértice de origem ou nó de origem “1” para “2”. O peso atual será 5 (5
Passo 5) Agora, se verificarmos as distâncias mais curtas do nó “1”, descobriremos que 5 é a distância mais curta para a aresta 1–> 2. Portanto, o nó “2” será marcado como visitado.
Da mesma forma, o nó “3” também será marcado como visitado, pois a distância mais curta é 3.
Porém, se observarmos, existe um caminho 1-3-2 que custará apenas 2. Mas o Dijkstra mostra que do nó “1” ao nó “2”, a distância mais curta é 5. Portanto, Dijkstra não conseguiu calcular o caminho mais curto. distância corretamente. A razão pela qual isso aconteceu é que Dijkstra é um algoritmo ganancioso. Assim, uma vez que um nó seja marcado como visitado, ele não será reconsiderado, embora possa haver um caminho mais curto disponível. Este problema só ocorre quando as arestas têm custos negativos ou arestas de peso negativo
Dijkstra não consegue calcular o caminho mais curto entre dois nós neste cenário. Como resultado, este algoritmo tem algumas desvantagens. Para resolver este problema de borda negativa, outro algoritmo chamado “Algoritmo Bellman-Ford” é usado. Esse algoritmo pode funcionar com arestas negativas.
Complexidade do algoritmo de Dijkstra
A implementação acima usou dois loops “for”. Esses loops são executados para o número de vértices. Então, a complexidade do tempo é O(V2). Aqui, o termo “0” significa uma notação que fornece uma suposição para o algoritmo de Dijkstra.
Podemos armazenar o gráfico usando a “Fila de prioridade”. Uma fila de prioridade é uma estrutura de dados heap binária. Será mais eficiente que uma matriz 2D. Uma vantagem que tenha um custo mínimo terá alta prioridade.
Então a complexidade do tempo será O (E log (V)). Aqui, E é o número de arestas e V é o número de vértices.
A complexidade do espaço é O(V2), pois estamos usando uma matriz de adjacência (Matriz 2D). A complexidade do espaço pode ser otimizada usando uma lista de adjacência ou uma estrutura de dados de fila.
