GrokkingAlgorithms/13 dijkstras algorithm hash.py at main · AlexTkDev/GrokkingAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# Алгоритм Дейкстры, используя хеш-таблицы (словари).
# [O(E*log V); V - количество вершин графа, E - количество ребер графа]
# Здесь нам нужно найти все кратчайшие пути от начального узла до всех остальных узлов
# в направленном ациклическом взвешенном графе.

# Создаем словарь "graph", который представляет из себя направленный ациклический взвешенный граф.
# Этот словарь особенный тем, что каждое его значение является словарем.
# Эти значения представляют из себя наборы соседних узлов каждого узла этого графа и их стоимостей.
graph = {"start": {"a": 6,
                   "b": 2},
         "a": {"fin": 1},
         "b": {"a": 3,
               "fin": 5},
         "fin": {}}


# Создаем переменную "infinity", которая хранит "бесконечность".
# Мы используем эту переменную, когда неизвестен путь до какого-либо узла.
infinity = float("inf")


# Создаем словарь "costs", который представляет из себя таблицу стоимостей
# путей от узла "start" до других узлов графа "graph".
# Указываем те стоимости, которые известны в начале работы алгоритма.
# В комментариях ниже указаны изменения значений после работы каждого цикла while,
# который находится внизу этой программы.
costs = {"a": 6,            # 5 - 5 - 5
         "b": 2,            # 2 - 2 - 2
         "fin": infinity}   # 7 - 6 - 6


# Создаем словарь "parents", который представляет из себя таблицу родителей каждого узла в графе "graph".
# Указываем тех родителей, которые известны в начале работы алгоритма.
# В комментариях ниже указаны изменения значений после работы каждого цикла while,
# который находится внизу этой программы.
parents = {"a": "start",    # "b"     - "b"     - "b"
           "b": "start",    # "start" - "start" - "start"
           "fin": None}     # "b"     - "a"     - "a"


# Создаем список "processed", в который мы добавляем уже обработанные узлы,
# чтобы избежать повторной обработки таких узлов.
# Изначально этот список пустой.
processed = []


# Создаем функцию "find_lowest_cost_node", которая принимает один входной параметр:
# словарь "table_of_costs", который представляет из себя таблицу стоимостей
# путей от начального узла до других узлов направленного ациклическего взвешенного графа.
# Эта функция возвращает имя узла с наименьшей стоимостью.
def find_lowest_cost_node(table_of_costs):
    # Создаем переменную "lowest_cost", которая хранит стоимость узла, который имеет наименьшую стоимость.
    # Изначально эта переменная хранит значение "бесконечность".
    lowest_cost = float("inf")
    # Создаем переменную "lowest_cost_node", которая хранит имя узла, который имеет наименьшую стоимость.
    # Изначально эта переменная хранит значение "None".
    lowest_cost_node = None
    # Создаем цикл for, в котором перебираем все ключи (узлы графа) словаря "table_of_costs".
    for key_node in table_of_costs:
        # Создаем переменную "value_cost", которая хранит значение (стоимость узла графа),
        # соответствующее текущему ключу.
        value_cost = table_of_costs[key_node]
        # Если стоимость текущего узла меньше стоимости узла, который имеет наименьшую стоимость,
        # и если мы еще не обрабатывали этот текущий узел, то
        if value_cost < lowest_cost and key_node not in processed:
            # считаем, что стоимость текущего узла является наименьшей,
            lowest_cost = value_cost
            # а также считаем, что этот узел является новым узлом, который имеет наименьшую стоимость.
            lowest_cost_node = key_node
    # В итоге работы этого цикла for функция "find_lowest_cost_node" возвращает имя узла с наименьшей стоимостью.
    # Ключевое слово "return" выходит из функции и возвращает какое-либо значение.
    return lowest_cost_node


# Находим имя узла с наименьшей стоимостью в словаре "costs" (изначально это узел "b").
# В комментариях ниже указаны изменения значений этой переменной после работы каждого цикла while,
# который находится внизу этой программы.
node = find_lowest_cost_node(costs)  # "a" - "fin" - None


# Высчитываем все кратчайшие пути от узла "start" до узлов "a", "b" и "fin"
# путем обновления словарей "costs" и "parents".
# Создаем цикл while, который работает пока переменная "node" не является пустой,
# то есть пока у нас есть узлы с наименьшей стоимостью для обработки.
while node is not None:
    # Создаем переменную "cost", которая хранит стоимость текущего узла с наименьшей стоимостью "node".
    cost = costs[node]
    # Создаем переменную "neighbors", которая хранит словарь, представляющий из себя
    # список соседних узлов текущего узла с наименьшей стоимостью "node" и их стоимости.
    neighbors = graph[node]
    # Создаем цикл for, в котором перебираем
    # ключи (имена всех соседних узлов текущего узла с наименьшей стоимостью "node") в словаре "neighbors".
    for neighbor_name in neighbors.keys():
        # Высчитываем новую стоимость пути от узла "start"
        # до текущего соседнего узла текущего узла с наименьшей стоимостью "node".
        new_cost = cost + neighbors[neighbor_name]
        # Если текущая стоимость пути от узла "start"
        # до текущего соседнего узла текущего узла с наименьшей стоимостью "node"
        # больше, чем новая стоимость этого пути, то
        if costs[neighbor_name] > new_cost:
            # обновляем текущую стоимость этого пути в словаре "costs",
            costs[neighbor_name] = new_cost
            # а также обновляем родителя текущего соседнего узла текущего узла с наименьшей стоимостью "node"
            # в словаре "parents".
            parents[neighbor_name] = node
    # Если мы перебрали все соседние узлы текущего узла с наименьшей стоимостью "node",
    # тогда мы добавляем этот узел в список "processed",
    processed.append(node)
    # находим следующий узел, который имеет наименьшую стоимость,
    # и работа этого цикла while продолжается с начала, используя этот новый узел.
    node = find_lowest_cost_node(costs)


# Выводим на экран обновленные словари "costs" и "parents".
# Функция "print()" выводит некую указанную информацию на экран или на какое-либо другое устройство вывода.
print(costs)
print(parents)