Алгоритм Дейкстры (Dijkstra’s Algorithm)

Алгоритм Дейкстры (Dijkstra’s Algorithm) Изучение

Иногда нам нужно найти связи между двумя разными углами, и тогда нам нужен график. В простом примере, если мы хотим перейти из одного места в другое, то карты Google показывают все разные пути, но выделяют кратчайший путь к месту назначения. Но если вы измените свой путь во время использования Google Map, тогда он предсказывает новый путь в соответствии с вашим текущим местоположением к месту назначения. Итак, все это происходит с помощью алгоритма, который мы назвали алгоритмом Дейкстры. Алгоритм Дейкстры находит кратчайший путь среди узлов.

В графе есть узлы и ребра. Узлы — это значения, а края — это путь или линии, которые создают связи между двумя узлами. В Python мы можем реализовать узлы и ребра, используя вложенный словарь. Мы можем представить узлы как ключ, а все пути от этого узла к другим узлам как значение этого конкретного ключа.

Алгоритм Дейкстры используется для поиска кратчайшего пути между исходным узлом и целевым узлом. Подход, который используется в этом алгоритме, называется жадным подходом. Итак, в этой статье мы собираемся понять концепции алгоритма Дейкстры и то, как мы можем реализовать его с помощью программирования на Python.

Алгоритм Дейкстры, как мы уже говорили, использует концепцию жадного подхода. Мы можем понять жадный подход в обычном смысле, который находит оптимальное решение из имеющихся вариантов.

Шаги алгоритма

  1. Сначала мы инициализируем значение 0 исходного узла и значения других соседних узлов как бесконечные.
  2. Вставьте исходный узел и значение расстояния как пару <node, dist> в словарь. Например, пара значений исходного узла будет <S, 0>. S представляет имя узла, а 0 — значение расстояния. Значение 0 связано с тем, что мы инициализируем значение 0 исходного узла.
  3. Цикл будет продолжаться до DICTIONARY, не нулевого (или не пустого).
  4. Мы назначили любую пару <node, dist> из DICTIONARY в current_source_node на основе следующего условия: Значение расстояния между узлами должно быть меньше, чем среди доступных значений расстояния до узлов. После этого удалите это из списка словарей, потому что теперь это current_source_node.
  5. Для каждогососеднего_link_node к current_source_node выполните
  6. Если(dist [соседний_ссылка_узел]> значение края от текущего_сходного_узла до соседнего узла + dist [текущий_source_node])
  7. dist [neighbour_link_node] = значение края от current_source_node до соседнего узла + dist [current_source_node]
  8. Затем обновите СЛОВАРЬ, добавив в него пару <имя_узла_смежной_ссылки, расстояние [узел_следующей_ссылки,]>

Шаги алгоритма Дейкстры

Алгоритм Дейкстры используется для поиска кратчайшего пути между исходным узлом и целевым узлом.

Шаг 1: Для этого мы должны сначала инициализировать исходный узел как 0, а другие узлы как ∞. Затем мы вставляем в словарь пару <node, dist of node from original source node>. Наша первая пара будет <0, 0>, потому что расстояние от источника до самого источника равно 0, как показано на графике и таблице ниже.

Для этого мы должны сначала инициализировать исходный узел как 0

Исходный узел Конечный узел Расстояние от узла источника Словарь
[0, 0]
1
2
3
4
5

Шаг 2: В словаре всего одна пара <0, 0>. Итак, мы принимаем это как current_source_node и ослабляем вес ребер всех смежных узлов из current_source_node (0).

Текущий узел источника Смежный узел Расстояние от источника (0) до соседнего узла Обновлять вес egde или нет
1 dist [1] = ∞ dist [1]> dist_between [0 — 1] + dist [0] т.е. ∞> 5 + 0 Итак, мы собираемся обновить расстояние. Обновите dist => dist [1] = 5 и обновите пару в dict <1, 5>
2 dist [2] = ∞ dist [2]> dist_between [0 — 2] + distance [0] т.е. ∞> 1 + 0 Итак, мы собираемся обновить расстояние. Обновите dist => dist [2] = 1 и обновите пару в dict <2, 1>
3 dist [3] = ∞ dist [3]> dist_between [0 — 3] + dist [0] Итак, мы собираемся обновить расстояние. т.е. ∞> 4 + 0 Обновить dist, т.е. dist [3] = 4 и обновить пару в dict <3, 4>

Итак, мы принимаем это как current_source_node и ослабляем вес ребер

Исходный узел Конечный узел Расстояние от узла источника Словарь
[1, 5]
[2, 1]
[3, 4]
1 5
2 1
3 4
4
5

Шаг 3: Теперь мы удаляем следующую пару из словаря для current_source_node. Но условием является то, что мы должны выбрать узел минимального значения расстояния. Итак, мы выбираем <2, 1> из словаря и назначаем current_source_node и ослабляем вес ребер всех соседних узлов из current_source_node (2).

Текущий узел источника Смежный узел Расстояние от источника (0) до соседнего узла Обновлять вес egde или нет
2 расстояние [0] = 0 dist [0] <dist_between [2 — 0] + dist [2], т.е. 0 <1 + 1 Обновление веса не требуется. dist [1]> dist_between [2–1] + dist [2] т.е. 5> 3 + 1
2 1 расстояние [1] = 5 Итак, мы собираемся обновить расстояние. Обновите dist ==> dist [1] = 4 и обновите пару в dict <1, 4> dist [3]> dist_between [2 — 3] + dist [2], т.е. 4> 2 + 1
2 3 расстояние [3] = 4 Итак, мы собираемся обновить расстояние. Обновите dist => dist [3] = 3 и обновите пару в dict <3, 3> dist [4]> dist_between [2–4] + dist [2], т.е. ∞> 1 + 1.
2 4 расстояние [4] = ∞ Итак, мы собираемся обновить расстояние. Обновить dist => dist [4] = 2 обновить пару в dict <4, 2>

Теперь мы удаляем следующую пару из словаря для current_source_node

Исходный узел Конечный узел Расстояние от узла источника Словарь
2 [1, 4]
[3, 3]
[4, 2]
2 1 4
2 2 1
2 3 3
2 4 2
2 5
Читайте также:  Что лучше SSD или HDD: сравнение

Шаг 4: Теперь мы удаляем следующую пару <4, 2> из словаря, чтобы выбрать current_source_node и ослабить вес ребер всех соседних узлов из current_source_node (4).

Текущий узел источника Смежный узел Расстояние от источника (0) до соседнего узла Обновлять вес egde или нет
4 1 dist [1] = 4 dist [1] <dist_between [4 — 1] + dist [4] т.е. 4 <8 + 2 Обновление веса не требуется.
4 2 dist [2] = 1 dist [2] <dist_between [4 — 2] + dist [4] т.е. 1 <1 + 2 Обновление веса не требуется.
4 3 dist [3] = 3 dist [3] <dist_between [4 — 3] + dist [4] т.е. 3 <2 + 2 Обновление веса не требуется.
4 5 dist [5] = ∞ Итак, мы собираемся обновить расстояние. Обновить dist => dist [5] = 5 обновить пару в dict <5, 5>

Теперь мы удаляем следующую пару 4, 2 из словаря, чтобы выбрать current_source_node

Исходный узел Конечный узел Расстояние от узла источника Словарь
4 [1, 4]
[3, 3]
[5, 5]
4 1 4
4 2 1
4 3 3
4 4 2
4 5 5

Шаг 5: Мы удаляем следующую пару <3, 3> из словаря, чтобы выбрать current_source_node и ослабить вес ребер всех соседних узлов из current_source_node (3).

Текущий узел источника Смежный узел Расстояние от источника (0) до соседнего узла Обновлять вес egde или нет
3 dist [0] = 0 dist [0] <dist_between [3 — 0] + dist [3] т.е. 0 <4 + 3 Обновление веса не требуется.
3 2 dist [2] = 1 dist [2] <dist_between [3 — 2] + dist [3] т.е. 1 <2 + 3 Обновление веса не требуется.
3 4 dist [4] = 2 dist [4] <dist_between [3-4] + dist [3] т.е. 2 <2 + 3 Обновление веса не требуется.
3 5 dist [5] = 5 Итак, мы собираемся обновить расстояние. Обновить dist => dist [5] = 4 обновить пару в dict <5, 4>

Мы удаляем следующую пару 3, 3 из словаря, чтобы выбрать current_source_node

Исходный узел Конечный узел Расстояние от узла источника Словарь
3 [1, 4]
[5, 4]
3 1 4
3 2 1
3 3 3
3 4 2
3 5 4

Шаг 6: Мы удаляем следующую пару <1, 4> из словаря, чтобы выбрать current_source_node и ослабить вес ребер всех соседних узлов из current_source_node (1).

Текущий узел источника Смежный узел Расстояние от источника (0) до соседнего узла Обновлять вес egde или нет
1 dist [0] = 0 distance [0] <distance_between [1 — 0] + distance [1], т.е. Поскольку 0 <5 + 4 Обновление веса не требуется.
1 2 dist [2] = 1 dist [2] <dist_between [1-2] + dist [1] т.е. 1 <3 + 4 Обновление веса не требуется.
1 4 dist [4] = 2 dist [4] <dist_between [1 — 4] + dist [1] т.е. 2 <8 + 4 Обновление веса не требуется.

Мы удаляем следующую пару 1, 4 из словаря, чтобы выбрать current_source_node

Исходный узел Конечный узел Расстояние от узла источника Словарь
1 [5, 4]
1 1 4
1 2 1
1 3 3
1 4 2
1 5 4

Шаг 7: Теперь мы удаляем следующую пару <5, 4> из словаря, чтобы выбрать current_source_node и ослабить вес ребер всех соседних узлов из current_source_node (5).

Текущий узел источника Смежный узел Расстояние от источника (0) до соседнего узла Обновлять вес egde или нет
5 3 dist [3] = 3 ddist [3] <dist_between [5 — 3] + dist [5] т.е. 3 <1 + 4 Обновление веса не требуется.
5 4 dist [4] = 2 dist [4] <dist_between [5 — 4] + dist [5] т.е. 2 <3 + 4 Обновление веса не требуется.

Теперь словарь равен нулю, и никаких пар не осталось. Итак, наш алгоритм остановлен. И мы получили кратчайший путь от основного узла-источника (S) ко всем остальным узлам, как показано ниже:

Теперь мы удаляем следующую пару 5, 4 из словаря, чтобы выбрать current_source_node

Исходный узел Конечный узел Расстояние от узла источника Словарь
1 4
2 1
3 3
4 2
5 4

Код Python : Ниже представлена ​​реализация вышеуказанного алгоритма.

1 # Dijkstra’s Algorithm in Python
2 from collections import defaultdict
3
4 class Node_Dist:
5    def __init__(self, name, dist) :
6        self.name = name
7        self.dist = dist
8
9 class DijkstraAlgorithm:
10
11    def __init__(self, node_count) :
12        self.adjacentlist = defaultdict(list)
13        self.node_count = node_count
14
15    def Adjacent_nodelist(self, src, node_dist) :
16        self.adjacentlist[src].append(node_dist)
17
18    def Dijkstras_Shortest_Path(self, source_node) :
19        # Initialize the nodes with infinite value and source
20        # node with 0
21       dist = [999999999999] * self.node_count
22        dist[source_node] = 
23
24        # we are creating a dict as said in the alogrithm with the
25        # value pair
26        dict_of_node_dist = {source_node: }
27
28        while dict_of_node_dist :
29
30            # Now, we are going to assing a pair  to a
31           # current_source_node but condition that dist value
32            # should be the minimum value
33            current_source_node = min(dict_of_node_dist,
34                                      key = lambda k: dict_of_node_dist[k])
35
36            # After assign that pair to the current_source_node,
37            # delete that item from the dict
38            del dict_of_node_dist[current_source_node]
39
40            for node_dist in self.adjacentlist[current_source_node] :
41                adjacentNode = node_dist.name
42                source_to_adjacentNode_dist = node_dist.dist
43
44                # We are doing here edge relaxation of the adjacent node
45                if dist[adjacentNode] > dist[current_source_node] + \
46                        source_to_adjacentNode_dist :
47                    dist[adjacentNode] = dist[current_source_node] + \
48                                         source_to_adjacentNode_dist
49                    dict_of_node_dist[adjacentNode] = dist[adjacentNode]
50
51        for i in range(self.node_count) :
52            print(«Distance From Source Node («+str(source_node)+«)  => to «
53                        «Destination Node(« + str(i) + «)  => « + str(dist[i]))
54
55 def main() :
56
57    graph = DijkstraAlgorithm(6)
58    graph.Adjacent_nodelist(, Node_Dist(1, 5))
59    graph.Adjacent_nodelist(, Node_Dist(2, 1))
60    graph.Adjacent_nodelist(, Node_Dist(3, 4))
61
62    graph.Adjacent_nodelist(1, Node_Dist(, 5))
63    graph.Adjacent_nodelist(1, Node_Dist(2, 3))
64    graph.Adjacent_nodelist(1, Node_Dist(4, 8))
65
66    graph.Adjacent_nodelist(2, Node_Dist(, 1))
67    graph.Adjacent_nodelist(2, Node_Dist(1, 3))
68    graph.Adjacent_nodelist(2, Node_Dist(3, 2))
69    graph.Adjacent_nodelist(2, Node_Dist(4, 1))
70
71    graph.Adjacent_nodelist(3, Node_Dist(, 4))
72    graph.Adjacent_nodelist(3, Node_Dist(2, 2))
73    graph.Adjacent_nodelist(3, Node_Dist(4, 2))
74    graph.Adjacent_nodelist(3, Node_Dist(5, 1))
75
76    graph.Adjacent_nodelist(4, Node_Dist(1, 8))
77    graph.Adjacent_nodelist(4, Node_Dist(2, 1))
78    graph.Adjacent_nodelist(4, Node_Dist(3, 2))
79    graph.Adjacent_nodelist(4, Node_Dist(5, 3))
80
81    graph.Adjacent_nodelist(5, Node_Dist(3, 1))
82    graph.Adjacent_nodelist(5, Node_Dist(4, 3))
83
84    graph.Dijkstras_Shortest_Path()
85
86
87 if __name__ == «__main__» :
88   main()

Строки с 9 по 53 : Объяснение этого класса приведено ниже:

Читайте также:  Python против Java: в чем разница?

Строка 9 : Мы создали класс под названием DijkstraAlgorithm.

Строки с 11 по 16 : мы инициализируем смежный список и node_count. Смежный список — это словарь, который мы использовали для хранения узла и всех соседних с ним узлов, например узла 0:. Этот код, если вы его распечатаете, покажет результат, как показано ниже:

defaultdict(<class ‘list’>, {})
defaultdict(<class ‘list’>, {[<__main__.Node_Dist object at 0x7f2b0a05abe0>]})

Приведенный выше результат показывает, что мы создаем dict, который содержит все детали конкретного узла и соседних с ним узлов.

Строки с 21 по 22 : мы инициализируем все узлы с бесконечным значением, а исходные узлы с 0 в соответствии с нашим алгоритмом.

Строка 26 : мы инициализируем dict_of_node_dist в соответствии с нашим алгоритмом, который является нашей первой парой.

Строки с 28 по 50 : Реализуем в соответствии с алгоритмом строки с 4 по 8.

Строки 57–83 : мы создали объект класса DijkstraAlgorithm и передали количество узлов в графе. Затем мы вызвали метод Adjacent_nodelist, используя граф объектов, чтобы сделать dict всех узлов с их соседними узлами. Узел будет ключевым, а соседние узлы, а расстояние — их значениями.

Строка 83 : Мы вызвали метод Dijkstras_Shortest_Path (0), используя граф объектов.

Выход : Python Dijkstra’s Algorithm.py

Расстояние от исходного узла (0) => до конечного узла (0) => 0
Расстояние от исходного узла (0) => до конечного узла (1) => 4
Расстояние от исходного узла (0) => до конечного узла (2) => 1
Расстояние от исходного узла (0) => до конечного узла (3) => 3
Расстояние от исходного узла (0) => до конечного узла (4) => 2
Расстояние от исходного узла (0) => до конечного узла (5) => 4

Заключение

В этой статье мы шаг за шагом изучили алгоритм Дейкстры. Мы также изучили идею жадного подхода.

Оцените статью
bestprogrammer.ru
Добавить комментарий