Algorytm Dijkstry

Czasami musimy znaleźć powiązania między dwoma różnymi zakątkami, a następnie potrzebujemy wykresu. W prostym przykładzie, jeśli chcemy przejść z jednego miejsca do drugiego, wówczas Mapy Google pokazują wszystkie różne sposoby, ale podkreśl najkrótszą ścieżkę do osiągnięcia miejsca docelowego. Ale jeśli zmienisz ścieżkę podczas korzystania z Map Google, wówczas przewiduje nową ścieżkę zgodnie z obecną lokalizacją do miejsca docelowego. Tak więc wszystko dzieje się przez algorytm, który nazywaliśmy algorytmem Dijkstry. Algorytm Dijkstry znajduje najkrótszą ścieżkę wśród węzłów.

Na wykresie istnieją węzły i krawędzie. Węzły to wartości, a krawędzie to ścieżka lub linie, które tworzą łącza między dwoma węzłami. W Python możemy zaimplementować węzły i krawędzie za pomocą zagnieżdżonego słownika. Możemy reprezentować węzły jako klucz i wszystkie ścieżki od tego węzła do innych węzłów jako wartości tego konkretnego klucza.

Algorytm Dijkstry służy do znalezienia najkrótszej ścieżki między węzłem źródłowym a węzłem docelowym. Podejście algorytm ten jest używany zwany chciwym podejściem. Tak więc w tym artykule zrozumiemy pojęcia algorytmu Dijkstry i tego, jak możemy go wdrożyć za pomocą programowania Python.

Algorytm Dijkstry, jak powiedzieliśmy wcześniej, stosuje koncepcję chciwego podejścia. Możemy zrozumieć chciwe podejście w normalnym terminie, które znajduje optymalne rozwiązanie z dostępnych opcji.

Kroki algorytmu

1. Najpierw zainicjujemy wartość węzła źródłowego 0 i inne sąsiednie węzły jako nieskończone.
2. Włóż węzeł źródłowy i wartość odległości jako para w słowniku. Na przykład para wartości węzła źródłowego będzie . S reprezentuje nazwę węzła, a 0 to wartość odległości. Wartość 0 wynosi, ponieważ inicjujemy wartość węzła źródłowego 0.
3. Pętla będzie kontynuować do słownika, a nie zerowego (lub nie pustego).
4. Przypisaliśmy dowolną parę ze słownika do Current_source_node w oparciu o następujący warunek:

Wartość odległości węzła powinna być mniejsza niż pośród dostępnych wartości odległości odległości. Następnie usuń to z listy słowników, ponieważ jest to teraz Current_source_node.

5. Dla każdego sąsiad_link_node z bieżącym_source_node do
6. Jeśli (Dist [Aviacent_Link_Node]> Wartość krawędzi od Current_Source_Node do sąsiedniego węzła+ Dist [Current_source_node]))
7. Dist [Aviacent_Link_Node] = Wartość krawędzi od Current_Source_Node do sąsiedniego węzła + Dist [Current_source_node]
8. Następnie zaktualizuj słownik parą

Algorytm Dijkstry

Algorytm Dijkstry służy do znalezienia najkrótszej ścieżki między węzłem źródłowym a węzłem docelowym.

Krok 1: W tym celu musimy najpierw zainicjować węzeł źródłowy jako 0 i inne węzły jako ∞. Następnie wkładamy parę do słownika. Nasza pierwsza para będzie miała miejsce, że odległość od źródła do samego źródła wynosi 0, jak pokazano na poniższym wykresie i tabeli.

Węzeł źródłowy	Węzeł docelowy	Odróżnij od węzła źródłowego	Słownik
0	0	0	[0, 0]
0	1	∞
0	2	∞
0	3	∞
0	4	∞
0	5	∞

Krok 2 W słowniku jest tylko jedna para . Tak więc bierzemy to jako Current_source_node i rozluźniamy wagę krawędzi wszystkich sąsiednich węzłów z Current_Source_Node (0).

Obecny węzeł źródłowy	Sąsiedni węzeł	Dist od źródła (0) do sąsiedniego węzła	Zaktualizuj wagę EGDE lub nie
0	1	Dist [1] = ∞	Dist [1]> Dist_between [0 - 1] + Dist [0] i.e ∞> 5 + 0 Więc zaktualizujemy odległość. Aktualizacja dist => Dist [1] = 5 i zaktualizuj parę w Dict
0	2	Dist [2] = ∞	Dist [2]> Dist_between [0 - 2] + odległość [0] i.e ∞> 1 + 0 Więc zaktualizujemy odległość. Aktualizacja dist => Dist [2] = 1 i zaktualizuj parę w Dict
0	3	Dist [3] = ∞	Dist [3]> Dist_between [0 - 3] + Dist [0] Więc zaktualizujemy odległość. I.e ∞> 4 + 0 aktualizacja Dist, i.mi Dist [3] = 4 i zaktualizuj parę w Dict

Węzeł źródłowy	Węzeł docelowy	Odróżnij od węzła źródłowego	Słownik
0	0	0	[1, 5] [2, 1] [3, 4]
0	1	5
0	2	1
0	3	4
0	4	∞
0	5	∞

Krok 3: Teraz usuwamy następną parę ze słownika dla Current_source_node. Ale warunek jest taki, że musimy wybrać minimalną wartość odległości. Tak więc wybieramy ze słownika i przypisaliśmy jako Current_Source_node i rozluźnij ciężar krawędzi wszystkich sąsiednich węzłów z Current_Source_Node (2).

Obecny węzeł źródłowy	Sąsiedni węzeł	Dist od źródła (0) do sąsiedniego węzła	Zaktualizuj wagę EGDE lub nie
2	0	odległość [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	odległość [1] = 5	Więc zamierzamy zaktualizować odległość. Aktualizacja Dist ==> Dist [1] = 4 i zaktualizuj parę w Dict Dist [3]> Dist_between [2 - 3] + Dist [2] i.E 4> 2 + 1
2	3	odległość [3] = 4	Więc zamierzamy zaktualizować odległość. Aktualizacja Dist => Dist [3] = 3 i zaktualizuj parę w Dict Dist [4]> Dist_between [2 - 4] + Dist [2] i.E ∞> 1 + 1
2	4	odległość [4] = ∞	Więc zamierzamy zaktualizować odległość. Aktualizacja dist => Dist [4] = 2 Zaktualizuj parę w DICT

Węzeł źródłowy	Węzeł docelowy	Odróżnij od węzła źródłowego	Słownik
2	0	0	[1, 4] [3, 3] [4, 2]
2	1	4
2	2	1
2	3	3
2	4	2
2	5	∞

Krok 4: Teraz usuwamy następną parę ze słownika, aby wybrać Current_Source_Node i rozluźnić wagę krawędzi wszystkich sąsiednich węzłów z Current_Source_Node (4).

Obecny węzeł źródłowy	Sąsiedni węzeł	Dist od źródła (0) do sąsiedniego węzła	Zaktualizuj wagę EGDE lub nie
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] = ∞	Więc zamierzamy zaktualizować odległość. Aktualizacja Dist => Dist [5] = 5 Zaktualizuj parę w DICT

Węzeł źródłowy	Węzeł docelowy	Odróżnij od węzła źródłowego	Słownik
4	0	0	[1, 4] [3, 3] [5, 5]
4	1	4
4	2	1
4	3	3
4	4	2
4	5	5

Krok 5: Usuwamy następną parę ze słownika, aby wybrać Current_Source_node i rozluźniamy wagę krawędzi wszystkich sąsiednich węzłów z Current_Source_Node (3).

Obecny węzeł źródłowy	Sąsiedni węzeł	Dist od źródła (0) do sąsiedniego węzła	Zaktualizuj wagę EGDE lub nie
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	Więc zamierzamy zaktualizować odległość. Aktualizacja dist =>Dist [5] = 4 Zaktualizuj parę w DICT

Węzeł źródłowy	Węzeł docelowy	Odróżnij od węzła źródłowego	Słownik
3	0	0	[1, 4] [5, 4]
3	1	4
3	2	1
3	3	3
3	4	2
3	5	4

Krok 6: Usuwamy następną parę ze słownika, aby wybrać Current_Source_Node i rozluźniamy wagę krawędzi wszystkich sąsiednich węzłów z Current_Source_Node (1).

Obecny węzeł źródłowy	Sąsiedni węzeł	Dist od źródła (0) do sąsiedniego węzła	Zaktualizuj wagę EGDE lub nie
1	0	Dist [0] = 0	odległość [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.

Węzeł źródłowy	Węzeł docelowy	Odróżnij od węzła źródłowego	Słownik
1	0	0	[5, 4]
1	1	4
1	2	1
1	3	3
1	4	2
1	5	4

Krok 7: Teraz usuwamy następną parę ze słownika, aby wybrać Current_Source_node i rozluźnić ciężar krawędzi wszystkich sąsiednich węzłów z Current_Source_Node (5).

Obecny węzeł źródłowy	Sąsiedni węzeł	Dist od źródła (0) do sąsiedniego węzła	Zaktualizuj wagę EGDE lub nie
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.

Teraz słownik jest zerowy i żadna para nie pozostaje. Więc nasz algorytm jest teraz zatrzymany. I mamy całą najkrótszą ścieżkę z głównego węzła źródłowego do wszystkich innych węzłów, jak pokazano poniżej:

Węzeł źródłowy	Węzeł docelowy	Odróżnij od węzła źródłowego	Słownik
0	0	0
0	1	4
0	2	1
0	3	3
0	4	2
0	5	4

Kod Pythona: Poniżej znajduje się implementacja powyższego algorytmu.

1 # Algorytm Dijkstry w Python
2 Z kolekcji import defaultdict
3
4 klasa node_dist:
5 def __init __ (jaźń, nazwa, dist):
6 Jaźni.Nazwa = nazwa
7 ja.Dist = Dist
8
9 klas Dijkstraalgorytm:
10
11 def __init __ (self, node_count):
12 Jaźni.sąsiadList = defaultdict (lista)
13 Jaźni.node_count = node_count
14
15 def sąsiaduje_nodelist (self, src, node_dist):
16 ja.sąsiadujący [src].append (node_dist)
17
18 def dijkstras_shortest_path (self, source_node):
19 # Zainicjuj węzły o nieskończonej wartości i źródła
20 # węzeł z 0
21 Dist = [999999999999] * Self.node_count
22 Dist [Source_node] = 0
23
24 # tworzymy dykt, jak powiedziano w alogrytmie z
25 # para wartości
26 DICT_OF_NODE_DIST = źródło_node: 0
27
28, podczas gdy DICT_OF_NODE_DIST:
29
30 # Teraz idziemy do tyłka do pary do
31 # current_source_node, ale warunek, który rozróżnia wartość
32 # powinien być minimalną wartością
33 Current_source_node = Min (Dict_Of_Node_Dist,
34 Key = Lambda K: DICT_OF_NODE_DIST [K])
35
36 # Po przypisaniu tej pary do bieżącego_source_node,
37 # Usuń ten element z DICT
38 Del DICT_OF_NODE_DIST [Current_source_node]
39
40 dla Node_dist in Self.sąsiadList [current_source_node]:
41 sąsiadnode = node_dist.nazwa
42 źródło_to_adjacentnode_dist = node_dist.dist
43
44 # robimy tutaj relaksowanie krawędzi sąsiedniego węzła
45 if Dist [sąsiadnode]> dist [current_source_node] + \
46 źródło_to_adjacentnode_dist:
47 Dist [sąsiadnode] = dist [current_source_node] + \
48 źródło_to_adjacentnode_dist
49 DICT_OF_NODE_DIST [sąsiadnode] = dist [sąsiadnode]
50
51 dla i w zasięgu (jaźń.node_count):
52 Drukuj („Odległość od węzła źródłowego (”+str (źródło_node)+”) => do”
53 „Węzeł docelowy („ + str (i) + ”) =>” + str (dist [i]))
54
55 def main ():
56
57 wykres = dijkstraalgorytm (6)
58 Wykres.Sąsiad_nodelist (0, node_dist (1, 5))
59 wykres.Sąsiad_nodelist (0, node_dist (2, 1))
60 wykresu.Sąsiad_nodelist (0, node_dist (3, 4))
61
62 Wykres.Sąsiad_nodelist (1, node_dist (0, 5))
63 wykres.Sąsiad_nodelist (1, node_dist (2, 3))
64 Wykres.Sąsiad_nodelist (1, node_dist (4, 8))
65
66 Wykres.Sąsiadent_nodelist (2, node_dist (0, 1))
67 wykres.Sąsiad_nodelist (2, Node_dist (1, 3))
68 Wykres.Sąsiad_nodelist (2, node_dist (3, 2))
69 wykres.Sąsiad_nodelist (2, Node_dist (4, 1))
70
71 Wykres.Sąsiad_nodelist (3, node_dist (0, 4))
72 Wykres.Sąsiad_nodelist (3, Node_dist (2, 2))
73 wykres.Sąsiad_nodelist (3, node_dist (4, 2))
74 Wykres.Sąsiad_nodelist (3, Node_dist (5, 1))
75
76 Wykres.Sąsiad_nodelist (4, node_dist (1, 8))
77 wykres.Sąsiad_nodelist (4, node_dist (2, 1))
78 Wykres.Sąsiad_nodelist (4, node_dist (3, 2))
79 wykres.Sąsiad_nodelist (4, Node_dist (5, 3))
80
81 Wykres.Sąsiad_nodelist (5, Node_dist (3, 1))
82 Wykres.Sąsiad_nodelist (5, Node_dist (4, 3))
83
84 Wykres.Dijkstras_shortest_path (0)
85
86
87 Jeśli __name__ == "__main__":
88 Main ()

Linia od 9 do 53: Wyjaśnienie tej klasy podano poniżej:

Linia 9: Stworzyliśmy klasę nazwę dijkstraalgorytm.

Linia 11 do 16: Inicjujemy sąsiadujący lis i node_count. Sąsiadująca to dykt, którego użyliśmy do przechowywania węzła i wszystkich ich sąsiednich węzłów, jak węzeł 0: . Ten kod, jeśli wydrukujesz, pokaże wynik jak poniżej:

Defaultdict (, )
Defaultdict (, 0: [<__main__.Node_Dist object at 0x7f2b0a05abe0>])

Powyższy wynik pokazuje, że tworzymy dykt, który zawiera wszystkie szczegóły określonego węzła i jego sąsiednich węzłów.

Linia 21 do 22: Zainicjujemy wszystkie węzły o wartości nieskończoności i węzłach źródłowych z 0 zgodnie z naszym algorytmem.

Linia 26: Zainicjujemy DICT_OF_NODE_DIST zgodnie z naszym algorytmem, który jest naszą pierwszą parą.

Linia 28 do 50: Wdrażamy zgodnie z wierszami algorytmu od 4 do 8.

Linia 57 do 83: Stworzyliśmy obiekt klasy dijkstraalgorytm i przekazaliśmy liczbę węzłów na wykresie. Następnie wywołaliśmy metodę sąsiadującą_nodelistę za pomocą wykresu obiektu, aby wykonać dykt wszystkich węzłów z ich sąsiednimi węzłami. Węzeł będzie kluczem i sąsiednimi węzłami, a odległość będą ich wartościami.

Linia 83: Nazwaliśmy metodę Dijkstras_Shortest_Path (0) za pomocą wykresu obiektowego.

Wyjście: Algorytm Pythona Dijkstry.py

1. Odległość od węzła źródłowego (0) => do węzła docelowego (0) => 0
2. Odległość od węzła źródłowego (0) => do węzła docelowego (1) => 4
3. Odległość od węzła źródłowego (0) => do węzła docelowego (2) => 1
4. Odległość od węzła źródłowego (0) => do węzła docelowego (3) => 3
5. Odległość od węzła źródłowego (0) => do węzła docelowego (4) => 2
6. Odległość od węzła źródłowego (0) => do węzła docelowego (5) => 4

Wniosek

W tym artykule studiowaliśmy algorytm Dijkstry krok po kroku. Badaliśmy także chciwe pomysłem podejścia. Nie podajemy szczegółów na temat chciwego podejścia, ponieważ wkrótce wrócimy do tego (chciwe podejście).

Kod tego artykułu jest dostępny pod linkiem GitHub:
https: // github.com/shekharpandey89/dijkstra-s-algorytm