Algoritmo de Dijkstra
No gráfico, existem nós e bordas. Os nós são os valores e as bordas são o caminho ou as linhas que criam links entre os dois nós. Em Python, podemos implementar os nós e bordas usando o dicionário aninhado. Podemos representar os nós como uma chave e todos os caminhos desse nó para outros nós como um valor dessa chave específica.
O algoritmo de Dijkstra é usado para encontrar o caminho mais curto entre o nó de origem e o nó de destino. A abordagem desse algoritmo é usada chamada de abordagem gananciosa. Então, neste artigo, vamos entender os conceitos do algoritmo de Dijkstra e como podemos implementá -lo usando a programação Python.
O algoritmo de Dijkstra, como dissemos antes, está usando o conceito de abordagem gananciosa. Podemos entender a abordagem gananciosa em um termo normal que encontra a solução ideal das opções disponíveis.
Etapas do algoritmo
- Primeiro inicializamos o valor do nó de origem 0 e outros valores de nós adjacentes como infinitos.
- Insira o nó de origem e o valor da distância como um par no dicionário. Por exemplo, o par de valor do nó de origem será . O S representa o nome do nó e 0 é o valor da distância. O valor 0 é porque inicializamos o valor do nó de origem 0.
- O laço continuará até o dicionário, não nulo (ou não vazio).
- Atribuímos qualquer par do dicionário a current_source_node com base na seguinte condição:
O valor da distância do nó deve ser menor que os valores de distância dos nós disponíveis. Depois disso, remova -o da lista de dicionários, porque agora é current_source_node.
- Para cada adjacent_link_node para o current_source_node
- Se (Dist [adjacent_link_node]> Valor da borda de current_source_node para o nó adjacente+ dist [current_source_node])
- Dist [adjacent_link_node] = Valor da borda de current_source_node para o nó adjacente + dist [current_source_node]
- Em seguida, atualize o dicionário com par
Etapas do algoritmo de Dijkstra
O algoritmo de Dijkstra é usado para encontrar o caminho mais curto entre o nó de origem e o nó de destino.
Passo 1: Para isso, temos que inicializar primeiro o nó de origem como 0 e outros nós como ∞. Então inserimos o par no dicionário. Nosso primeiro par será porque a distância da fonte à própria fonte é 0, como mostrado no gráfico e tabela abaixo.
| Nó de origem | Nó de destino | Dist do nó de origem | Dicionário |
|---|---|---|---|
| 0 | 0 | 0 | [0, 0] |
| 0 | 1 | ∞ | |
| 0 | 2 | ∞ | |
| 0 | 3 | ∞ | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
Passo 2 No dicionário, há apenas um par . Então, tomamos isso como um current_source_node e relaxamos o peso das bordas de todos os nós adjacentes do current_source_node (0).
| nó de origem atual | Nó adjacente | Dist da fonte (0) ao nó adjacente | Atualizar o peso de Egde ou não |
|---|---|---|---|
| 0 | 1 | dist [1] = ∞ | dist [1]> dist_between [0 - 1] + dist [0] i.e ∞> 5 + 0 Então, vamos atualizar a distância. Atualizar dist => dist [1] = 5 e atualize o par no ditado |
| 0 | 2 | dist [2] = ∞ | dist [2]> dist_between [0 - 2] + distância [0] i.e ∞> 1 + 0 Então, vamos atualizar a distância. Atualizar dist => dist [2] = 1 e atualize o par no ditado |
| 0 | 3 | dist [3] = ∞ | dist [3]> dist_between [0 - 3] + dist [0], então vamos atualizar a distância. eu.e ∞> 4 + 0 update dist, i.e dist [3] = 4 e atualize o par no ditado |
| Nó de origem | Nó de destino | Dist do nó de origem | Dicionário |
|---|---|---|---|
| 0 | 0 | 0 | [1, 5] [2, 1] [3, 4] |
| 0 | 1 | 5 | |
| 0 | 2 | 1 | |
| 0 | 3 | 4 | |
| 0 | 4 | ∞ | |
| 0 | 5 | ∞ |
etapa 3: Agora, removemos o próximo par do dicionário para o current_source_node. Mas a condição é que, temos que escolher o nó de valor de distância mínimo. Então, escolhemos o dicionário e atribuídos como um current_source_node e relaxamos o peso das bordas de todos os nós adjacentes do current_source_node (2).
| nó de origem atual | Nó adjacente | Dist da fonte (0) ao nó adjacente | Atualizar o peso de Egde ou não |
|---|---|---|---|
| 2 | 0 | Distância [0] = 0 | Dist [0] < dist_between [ 2 - 0 ] + dist [ 2 ] i.e 0 dist_between [ 2 - 1 ] + dist [ 2 ] i.e 5 > 3 + 1 |
| 2 | 1 | Distância [1] = 5 | Então, vamos atualizar a distância. Atualizar dist ==> dist [1] = 4 e atualize o par no ditado dist [3]> dist_between [2 - 3] + dist [2] I.e 4> 2 + 1 |
| 2 | 3 | Distância [3] = 4 | Então, vamos atualizar a distância. Atualizar dist => dist [3] = 3 e atualize o par no ditado dist [4]> dist_between [2 - 4] + dist [2] I.e ∞> 1 + 1 |
| 2 | 4 | Distância [4] = ∞ | Então, vamos atualizar a distância. Atualizar dist => dist [4] = 2 Atualize o par no ditado |
| Nó de origem | Nó de destino | Dist do nó de origem | Dicionário |
|---|---|---|---|
| 2 | 0 | 0 | [1, 4] [3, 3] [4, 2] |
| 2 | 1 | 4 | |
| 2 | 2 | 1 | |
| 2 | 3 | 3 | |
| 2 | 4 | 2 | |
| 2 | 5 | ∞ |
Passo 4: Agora, removemos o próximo par do dicionário para escolher current_source_node e relaxar o peso das bordas de todos os nós adjacentes do current_source_node (4).
| nó de origem atual | Nó adjacente | Dist da fonte (0) ao nó adjacente | Atualizar o peso de Egde ou não |
|---|---|---|---|
| 4 | 1 | dist [1] = 4 | Dist [1] < dist_between [ 4 - 1 ] + dist [ 4 ] i.e 4 < 8 + 2 No weight updation required. |
| 4 | 2 | dist [2] = 1 | Dist [2] < dist_between [ 4 - 2 ] + dist [ 4 ] i.e 1 < 1 + 2 No weight updation required. |
| 4 | 3 | dist [3] = 3 | Dist [3] < dist_between [ 4 - 3 ] + dist [ 4 ] i.e 3 < 2 + 2 No weight updation required. |
| 4 | 5 | dist [5] = ∞ | Então, vamos atualizar a distância. Atualizar dist => dist [5] = 5 Atualize o par no ditado |
| Nó de origem | Nó de destino | Dist do nó de origem | Dicionário |
|---|---|---|---|
| 4 | 0 | 0 | [1, 4] [3, 3] [5, 5] |
| 4 | 1 | 4 | |
| 4 | 2 | 1 | |
| 4 | 3 | 3 | |
| 4 | 4 | 2 | |
| 4 | 5 | 5 |
Etapa 5: Removemos o próximo par do dicionário para escolher current_source_node e relaxar o peso das bordas de todos os nós adjacentes do current_source_node (3).
| nó de origem atual | Nó adjacente | Dist da fonte (0) ao nó adjacente | Atualizar o peso de Egde ou não |
|---|---|---|---|
| 3 | 0 | dist [0] = 0 | Dist [0] < dist_between [ 3 - 0 ] + dist [ 3 ] i.e 0 < 4 + 3 No weight updation required. |
| 3 | 2 | dist [2] = 1 | Dist [2] < dist_between [ 3 - 2 ] + dist [ 3 ] i.e 1 < 2 + 3 No weight updation required. |
| 3 | 4 | dist [4] = 2 | Dist [4] < dist_between [ 3 - 4 ] + dist [ 3 ] i.e 2 < 2 + 3 No weight updation required. |
| 3 | 5 | dist [5] = 5 | Então, vamos atualizar a distância. Atualizar dist =>dist [5] = 4 Atualize o par no ditado |
| Nó de origem | Nó de destino | Dist do nó de origem | Dicionário |
|---|---|---|---|
| 3 | 0 | 0 | [1, 4] [5, 4] |
| 3 | 1 | 4 | |
| 3 | 2 | 1 | |
| 3 | 3 | 3 | |
| 3 | 4 | 2 | |
| 3 | 5 | 4 |
Etapa 6: Removemos o próximo par do dicionário para escolher current_source_node e relaxar o peso das bordas de todos os nós adjacentes do current_source_node (1).
| nó de origem atual | Nó adjacente | Dist da fonte (0) ao nó adjacente | Atualizar o peso de Egde ou não |
|---|---|---|---|
| 1 | 0 | dist [0] = 0 | Distância [0] < distance_between [ 1 - 0 ] + distance [ 1 ] i.e Since 0 < 5 + 4 No weight updation required. |
| 1 | 2 | dist [2] = 1 | Dist [2] < dist_between [ 1 - 2 ] + dist [ 1 ] i.e 1 < 3 + 4 No weight updation required. |
| 1 | 4 | dist [4] = 2 | Dist [4] < dist_between [ 1 - 4 ] + dist [ 1 ] i.e 2 < 8 + 4 No weight updation required. |
| Nó de origem | Nó de destino | Dist do nó de origem | Dicionário |
|---|---|---|---|
| 1 | 0 | 0 | [5, 4] |
| 1 | 1 | 4 | |
| 1 | 2 | 1 | |
| 1 | 3 | 3 | |
| 1 | 4 | 2 | |
| 1 | 5 | 4 |
Etapa 7: Agora, removemos o próximo par do dicionário para escolher current_source_node e relaxar o peso das bordas de todos os nós adjacentes do current_source_node (5).
| nó de origem atual | Nó adjacente | Dist da fonte (0) ao nó adjacente | Atualizar o peso de Egde ou não |
|---|---|---|---|
| 5 | 3 | dist [3] = 3 | DDIST [3] < dist_between [ 5 - 3 ] + dist [ 5 ] i.e 3 < 1 + 4 No weight updation required. |
| 5 | 4 | dist [4] = 2 | Dist [4] < dist_between [ 5 - 4 ] + dist [ 5 ] i.e 2 < 3 + 4 No weight updation required. |
Agora, o dicionário é nulo e nenhum par deixado para trás. Então, nosso algoritmo agora está parado. E obtivemos todo o caminho mais curto do (s) nó (s) principal (s) principal (s) para todos os outros nós, como mostrado abaixo:
| Nó de origem | Nó de destino | Dist do nó de origem | Dicionário |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 4 | |
| 0 | 2 | 1 | |
| 0 | 3 | 3 | |
| 0 | 4 | 2 | |
| 0 | 5 | 4 |
Código Python: Abaixo está a implementação do algoritmo acima.
1 # Algoritmo de Dijkstra em Python2 De coleções importantes defaultDict
3
4 classe node_dist:
5 def __init __ (self, nome, dist):
6 self.nome = nome
7 self.dist = dist
8
9 Classe Dijkstraalgorithm:
10
11 def __init __ (self, node_count):
12 self.adjacentlist = defaultDict (lista)
13 self.node_count = node_count
14
15 def adjacent_nodelist (self, src, node_dist):
16 eu.Lista adjacentada [SRC].Anexar (node_dist)
17
18 DEF Dijkstras_shortest_path (self, fonte_node):
19 # Inicialize os nós com valor infinito e fonte
20 # nó com 0
21 dist = [9999999999999] * self.node_count
22 DIST [fonte_node] = 0
23
24 # estamos criando um ditado como dito no alogritmo com o
25 # par de valores
26 dict_of_node_dist = fonte_node: 0
27
28 enquanto dict_of_node_dist:
29
30 # agora, vamos assar um par para um
31 # current_source_node, mas condição esse valor dist
32 # deve ser o valor mínimo
33 current_source_node = min (dict_of_node_dist,
34 key = lambda k: dict_of_node_dist [k])
35
36 # Depois de atribuir esse par ao current_source_node,
37 # Exclua esse item do ditado
38 del dict_of_node_dist [current_source_node]
39
40 para node_dist em si mesmo.adjacentlist [current_source_node]:
41 adjacentNode = node_dist.nome
42 fonte_to_adjacentnode_dist = node_dist.dist
43
44 # estamos fazendo aqui o relaxamento da borda do nó adjacente
45 se dist [adjacentNode]> dist [current_source_node] + \
46 fonte_to_adjacentnode_dist:
47 dist [adjacentNode] = dist [current_source_node] + \
48 fonte_to_adjacentnode_dist
49 dict_of_node_dist [adjacentNode] = dist [adjacentNode]
50
51 para i no alcance (self.node_count):
52 Print ("Distância do nó de origem ("+str (fonte_node)+") => para"
53 "Nó de destino (" + str (i) + ") =>" + str (dist [i]))
54
55 def main ():
56
57 Gráfico = DijkstraalGorithm (6)
58 gráfico.Adjacent_nodelist (0, node_dist (1, 5))
59 gráfico.Adjacent_nodelist (0, node_dist (2, 1))
60 Gráfico.Adjacent_nodelist (0, node_dist (3, 4))
61
62 gráfico.Adjacent_nodelist (1, node_dist (0, 5))
63 gráfico.Adjacent_nodelist (1, node_dist (2, 3))
64 Gráfico.Adjacent_nodelist (1, node_dist (4, 8))
65
66 gráfico.Adjacent_nodelist (2, node_dist (0, 1))
67 Gráfico.Adjacent_nodelist (2, node_dist (1, 3))
68 gráfico.Adjacent_nodelist (2, node_dist (3, 2))
69 Gráfico.Adjacent_nodelist (2, node_dist (4, 1))
70
71 Gráfico.Adjacent_nodelist (3, node_dist (0, 4))
72 gráfico.Adjacent_nodelist (3, node_dist (2, 2))
73 gráfico.Adjacent_nodelist (3, node_dist (4, 2))
74 gráfico.Adjacent_nodelist (3, node_dist (5, 1))
75
76 gráfico.Adjacent_nodelist (4, node_dist (1, 8))
77 gráfico.Adjacent_nodelist (4, node_dist (2, 1))
78 gráfico.Adjacent_nodelist (4, node_dist (3, 2))
79 gráfico.Adjacent_nodelist (4, node_dist (5, 3))
80
81 gráfico.Adjacent_nodelist (5, node_dist (3, 1))
82 gráfico.Adjacent_nodelist (5, node_dist (4, 3))
83
84 gráfico.Dijkstras_shortest_path (0)
85
86
87 se __name__ == "__mAin__":
88 Main ()
Linha 9 a 53: A explicação desta classe é dada abaixo:
Linha 9: Criamos uma classe o nome Dijkstraalgorithm.
Linha 11 a 16: Inicializamos a lista adjacentList e Node_Count. A lista adjacentada é um ditado que usamos para armazenar o nó e todos os seus nós adjacentes, como o nó 0: . Este código, se você imprimir, mostrará o resultado como abaixo:
DefaultDict (DefaultDict (
O resultado acima mostra que estamos criando um ditado que tem todos os detalhes de um nó específico e seus nós adjacentes.
Linha 21 a 22: Inicializamos todos os nós com um valor infinito e nós de origem com 0 conforme nosso algoritmo.
Linha 26: Inicializamos o dict_of_node_dist de acordo com o nosso algoritmo, que é o nosso primeiro par.
Linha 28 a 50: Implementamos de acordo com as linhas de algoritmo 4 a 8.
Linha 57 a 83: Criamos um objeto da classe dijkstraalgorithm e passamos o número de nós no gráfico. Então chamamos o método adjacent_nodelist usando o gráfico de objeto para fazer um ditado de todos os nós com seus nós adjacentes. O nó será a chave e nós adjacentes e a distância serão seus valores.
Linha 83: Chamamos o método dijkstras_shortest_path (0) usando o gráfico do objeto.
Saída: Algoritmo de Python Dijkstra.py
- Distância do nó de origem (0) => até o nó de destino (0) => 0
- Distância do nó de origem (0) => até o nó de destino (1) => 4
- Distância do nó de origem (0) => até o nó de destino (2) => 1
- Distância do nó de origem (0) => até o nó de destino (3) => 3
- Distância do nó de origem (0) => até o nó de destino (4) => 2
- Distância do nó de origem (0) => até o nó de destino (5) => 4
Conclusão
Neste artigo, estudamos o algoritmo de Dijkstra passo a passo. Também estudamos a ideia de abordagem gananciosa. Não incluímos os detalhes sobre a abordagem gananciosa, porque voltaremos a esse tópico (abordagem gananciosa) mais tarde em breve.
O código deste artigo está disponível no link do GitHub:
https: // github.com/shekharpandey89/dijkstra-s-algorithm