Algoritmo de Dijkstra em Python & C++ (Exemplo)

O que é o caminho mais curto ou a menor distância?

Um caminho do vértice de origem ao vértice de destino que custa o mínimo é o caminho mais curto ou a menor distância. Em teoria dos grafos, é possível haver múltiplas rotas de uma origem a um destino. Dentre essas rotas, se houver uma que custe o mínimo, chamamos essa rota de caminho mais curto.

Aqui, "custo" significa o número de nós na rota ou a soma dos custos em cada aresta. 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 o Algoritmo de Dijkstra e o Algoritmo de Bellman-Ford.

Aqui, discutiremos o Algoritmo de Dijkstra. Vejamos o seguinte grafo ponderado:

Um gráfico ponderado não direcionado

• O termo "ponderado" significa o custo de deslocamento de um nó para outro. Por exemplo, ao deslocar-se 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 se mover de um nó para outro e voltar ao nó anterior. Portanto, se tentarmos encontrar todas as rotas do nó 1 ao nó 7, elas serão:

Dentre essas quatro rotas, podemos ver que a primeira rota custa 7. Portanto, é o caminho mais curto em termos de custo.

Caminho mais curto

Como funciona o algoritmo de Dijkstra

O algoritmo de Dijkstra consegue encontrar a menor distância em grafos direcionados e não direcionados ponderados. Este algoritmo é guloso porque sempre escolhe o nó mais curto ou mais próximo da origem. O termo "guloso" significa que, dentre um conjunto de resultados possíveis, o algoritmo escolherá o melhor deles.

Aqui, estamos tentando encontrar os caminhos mais curtos entre todas as rotas possíveis. Portanto, o Algoritmo de Dijkstra encontra todos os caminhos mais curtos a partir de um único nó de origem. Como resultado, ele se comporta como um algoritmo. 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 os demais nós com custo infinito.
Passo 2) Mantenha um array ou lista para guardar track dos 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 (demonstrado na seção de exemplos).
Passo 4) Continue o passo 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 é um algoritmo de busca do caminho mais curto, enquanto BFS e DFS são algoritmos de busca de caminho em geral. Em casos gerais, BFS e DFS não consideram o custo das arestas ao encontrar o caminho. Portanto, esses algoritmos não podem garantir o caminho mais curto.

Demonstração em grade 2D de como funciona o BFS (Buffering Forward System - Sistema de Busca em Largura de Banda)

Algosketch, mostrando demonstração de BFS

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.

Vejamos um exemplo de gráfico:

Aqui, a BFS encontra um caminho no nível 2. A BFS percorre o grafo em ordem de níveis. Portanto, ela percorre o grafo da seguinte forma:

Passo 1) Comece pelo nó “1” e visite todos os nós adjacentes 2, 3, 4.

Passo 2) Marque os nós 2, 3 e 4 como nível 1 e visite os nós adjacentes a eles. O algoritmo continuará explorando todos os nós adjacentes até alcançar o 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, a DFS calcula o custo do caminho com base no número de arestas. A 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.

No entanto, em termos do Algoritmo de Dijkstra, ele escolhe as arestas com base em seu custo. Como um algoritmo guloso, ele escolherá os caminhos de menor custo.

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.

O algoritmo de Dijkstra encontra os caminhos mais curtos calculando pesos. Ele não busca 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 nó 7.

Para este processo, as etapas são fornecidas abaixo:

Passo 1) Inicialize o custo do nó inicial com 0. Atribua “Inf” para os demais nós. Significa que não existe caminho entre a origem e o nó, ou que o caminho ainda não foi percorrido.

Passo 2) Ao selecionar o nó 1, ele será marcado como visitado. Em seguida, atualize todos os vizinhos adjacentes do nó 1. Os nós 2, 3 e 4 são os 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, estamos no nó 1 e precisamos atualizar o custo dos nós adjacentes 2, 3 e 4. Após a atualização, os custos ficarão assim:

Passo 3) Para o nó “2”, os vizinhos são 6 e 3. Estamos atualizando o custo em “6” comparando o infinito (valor atual) com o custo do nó 2 mais o custo do caminho de 2 até 6. Simplificando, 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.

Passo 4) Para o nó 3, o nó vizinho é o 7. Portanto, comparando o valor atual do nó 7 com o custo do caminho (7+1) ou 8, atualizaremos o custo do nó 7. Ou seja, 8. Assim, encontramos um caminho do nó 1 ao nó 7, que é 1→3→7. O custo é 8.

Passo 5) Para o nó 4, atualizaremos o custo do nó adjacente de acordo. Assim, o nó “5” terá um custo atualizado de 8. Após as etapas 4 e 5, ficará assim:

Agora, o caminho 1-3-7 tem um 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” tinha um custo de 4. Portanto, o caminho 1-2-6-7 terá um custo de 7.

Como 7 < 8, 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 era 8. Portanto, o grafo final terá a seguinte aparência:

A aresta marcada com uma linha preta é o nosso caminho mais curto de 1 a 7 e nos custará 7.

Apelido Code Algoritmo de Dijkstra

Segue o pseudocódigo do algoritmo de Dijkstra:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ Implementação do 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] && 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] && graph[U][j] &&
          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 do Algoritmo de Dijkstra

Para implementar o algoritmo de Dijkstra usando PythonAqui 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] <= _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 < 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 a partir do nó de origem.

Aplicação do Algoritmo Dijkstra

O algoritmo de Dijkstra possui uma ampla gama de aplicações. Entre elas, é amplamente utilizado na área de redes. Aqui estão alguns exemplos práticos de uso do algoritmo de Dijkstra:

Dijkstra em Google Mapas: Este algoritmo é a base para encontrar os caminhos mais curtos, como podemos ver no trecho de código acima.

Google Não utiliza o algoritmo de Dijkstra simples. Em vez disso, usa uma versão modificada. Ao selecionar um destino, são exibidos vários caminhos em Google Mapas. Dentre esses caminhos, alguns são selecionados para o usuário. Esses caminhos são escolhidos com base no "tempo". Portanto, o "tempo" é o custo da aresta para o caminho mais curto.

Dijkstra no roteamento IP: Roteamento IP Roteamento IP é uma terminologia de redes. Descreve como um pacote de dados é enviado ao destinatário por meio de diferentes caminhos. Esses caminhos consistem em roteadores, servidores e outros equipamentos. 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 dos protocolos é “OSPF (Open Shortest Path First)”. O OSPF utiliza o algoritmo de Dijkstra. O roteador mantém uma tabela de rotas. Cada roteador compartilha sua tabela com os roteadores vizinhos. Após receber a tabela atualizada, eles devem recalcular todos os caminhos. Nesse momento, o roteador utiliza o algoritmo de Dijkstra.

Limitação do Algoritmo de Dijkstra

O algoritmo de Dijkstra não garante o caminho mais curto em um grafo com arestas negativas. O algoritmo de Dijkstra segue estes princípios:

• 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 da esquerda, Existem três vértices. O algoritmo de Dijkstra será executado no grafo 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 infinita, pois o caminho mais curto ainda não foi calculado. Portanto, qualquer caminho que custe menos que infinito será adicionado ao caminho mais curto (abordagem gulosa).

Passo 4) Atualizando a distância do vértice de origem “1” para “2”. O peso atual será 5 (5 < infinito). Da mesma forma, atualize a distância do nó “1” para “3” com o peso 3.

Passo 5) Agora, se verificarmos as distâncias mais curtas a partir 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.

No entanto, se observarmos, existe um caminho 1-3-2 que custa apenas 2. Mas o algoritmo de Dijkstra mostra que, do nó "1" ao nó "2", a distância mais curta é 5. Portanto, o algoritmo de Dijkstra falhou ao calcular a distância mais curta corretamente. Isso ocorre porque o algoritmo de Dijkstra é um algoritmo guloso. Assim, uma vez que um nó é marcado como visitado, ele não será reconsiderado, mesmo que exista um caminho mais curto disponível. Esse problema só ocorre quando as arestas têm custos negativos ou pesos negativos.

Nesse cenário, o algoritmo de Dijkstra falha ao calcular o caminho mais curto entre dois nós. Consequentemente, esse algoritmo apresenta algumas desvantagens. Para solucionar esse problema de arestas negativas, utiliza-se outro algoritmo chamado "Algoritmo de Bellman-Ford". Esse algoritmo é capaz de lidar 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(V²)Aqui, o termo “O” é uma notação que indica uma suposição para o algoritmo de Dijkstra.

Podemos armazenar o grafo usando uma “fila de prioridade”. Uma fila de prioridade é uma estrutura de dados binária (heap). Ela será mais eficiente do que uma matriz 2D. Uma aresta com custo mínimo terá alta prioridade. Assim, a complexidade de tempo será O(n log n). 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(V²), 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.

Perguntas Frequentes