На этом шаге мы приведем реализацию этого алгоритма.
Алгоритм Дейкстры решает задачу поиска кратчайшего пути из одной вершины. Задается начальная вершина, и алгоритм возвращает путь с наименьшим весом к любой другой вершине во взвешенном графе. Он также возвращает минимальный общий вес для пути из начальной вершины к каждой из оставшихся. Алгоритм Дейкстры начинается из одной исходной вершины, а затем постоянно исследует ближайшие к ней вершины. По этой причине алгоритм Дейкстры, как и алгоритм Ярника, является жадным. Когда алгоритм Дейкстры исследует новую вершину, он проверяет, как далеко она находится от начальной вершины, и обновляет это значение, если находит более короткий путь. Подобно алгоритму поиска в ширину, он отслеживает, какие ребра ведут к каждой вершине.
Алгоритм Дейкстры выполняет такие шаги.
- Добавить начальную вершину в очередь с приоритетом.
- Извлечь из очереди с приоритетом ближайшую вершину (вначале это только исходная вершина) - назовем ее текущей.
- Исследовать все соседние вершины, связанные с текущей. Если они ранее не были записаны или если ребро предлагает новый кратчайший путь, то для каждой из этих вершин записать расстояние до начальной вершины, указать ребро, соответствующее этому расстоянию, и добавить новую вершину в очередь с приоритетом.
- Повторять шаги 2 и 3, пока очередь с приоритетом не опустеет.
- Вернуть кратчайшее расстояние до каждой вершины от начальной и путь, позволяющий добраться до каждой из них.
Код алгоритма Дейкстры включает в себя DijkstraNode - простую структуру данных для отслеживания затрат, связанных с каждой исследованной вершиной, и сравнения вершин. Это похоже на класс Node, который приведен на 26 шаге. Он также включает в себя вспомогательные функции для преобразования возвращенного массива расстояний во что-то более простое, удобное для поиска по вершине и вычисления кратчайшего пути до конкретной конечной вершины из словаря путей, возвращаемого dijkstra().
Чем долго рассуждать, лучше сразу приведем код алгоритма Дейкстры. Разберем его построчно.
from __future__ import annotations from typing import TypeVar, List, Optional, Tuple, Dict from dataclasses import dataclass from pr59_1 import WeightedPath, print_weighted_path from pr55_1 import WeightedGraph from weighted_edge import WeightedEdge from priority_queue import PriorityQueue V = TypeVar('V') # тип вершин в графе @dataclass class DijkstraNode: vertex: int distance: float def __lt__(self, other: DijkstraNode) -> bool: return self.distance < other.distance def __eq__(self, other: DijkstraNode) -> bool: return self.distance == other.distance def dijkstra(wg: WeightedGraph[V], root: V) -> Tuple[List[Optional[float]], Dict[int, WeightedEdge]]: first: int = wg.index_of(root) # найти начальную вершину # вначале расстояния неизвестны distances: List[Optional[float]] = [None] * wg.vertex_count distances[first] = 0 # корневая вершина равна 0 path_dict: Dict[int, WeightedEdge] = {} # как добраться до каждой вершины pq: PriorityQueue[DijkstraNode] = PriorityQueue() pq.push(DijkstraNode(first, 0)) while not pq.empty: u: int = pq.pop().vertex # исследовать ближайшую вершину dist_u: float = distances[u] # это мы уже, должно быть, видели # рассмотреть все ребра и вершины для данной вершины for we in wg.edges_for_index(u): # старое расстояние до этой вершины dist_v: float = distances[we.v] # старого расстояния не существует или найден более короткий путь if dist_v is None or dist_v > we.weight + dist_u: # изменить расстояние до этой Вершины distances[we.v] = we.weight + dist_u # заменить ребро на более короткий путь к этой вершине path_dict[we.v] = we # вскоре мы это проверим pq.push(DijkstraNode(we.v, we.weight + dist_u)) return distances, path_dict # Вспомогательная функция для удобного доступа к результатам # алгоритма Дейкстры def distance_array_to_vertex_dict(wg: WeightedGraph[V], distances: List[Optional[float]]) -> Dict[V, Optional[float]]: distance_dict: Dict[V, Optional[float]] = {} for i in range(len(distances)): distance_dict[wg.vertex_at(i)] = distances[i] return distance_dict # Принимает словарь ребер, позволяющих достичь каждого узла, # и возвращает список ребер от start до епd def path_dict_to_path(start: int, end: int, path_dict: Dict[int, WeightedEdge]) -> WeightedPath: if len(path_dict) == 0: return [] edge_path: WeightedPath = [] e: WeightedEdge = path_dict[end] edge_path.append(e) while e.u != start: e = path_dict[e.u] edge_path.append(e) return list(reversed(edge_path))
В первых строках dijkstra() используются структуры данных, с которыми вы уже знакомы, за исключением distances - заполнителя для расстояний до каждой вершины графа от root. Первоначально все эти расстояния равны None, потому что мы еще не знаем значения каждого из них, - именно для их определения мы применяем алгоритм Дейкстры!
def dijkstra(wg: WeightedGraph[V], root: V) -> Tuple[List[Optional[float]], Dict[int, WeightedEdge]]: first: int = wg.index_of(root) # найти начальную вершину # вначале расстояния неизвестны distances: List[Optional[float]] = [None] * wg.vertex_count distances[first] = 0 # корневая вершина равна 0 path_dict: Dict[int, WeightedEdge] = {} # как добраться до каждой вершины pq: PriorityQueue[DijkstraNode] = PriorityQueue() pq.push(DijkstraNode(first, 0))
Первый узел, помещенный в очередь с приоритетом, содержит корневую вершину.
while not pq.empty:
u: int = pq.pop().vertex # исследовать ближайшую вершину
dist_u: float = distances[u] # это мы уже, должно быть, видели
Мы будем выполнять алгоритм Дейкстры до тех пор, пока очередь с приоритетом не опустеет. u - текущая вершина, с которой начинается поиск, a dist_u - сохраненное расстояние, позволяющее добраться до u по известным маршрутам. Все вершины, исследованные на этом этапе, уже найдены, поэтому для них расстояние уже известно.
# рассмотреть все ребра и вершины для данной вершины
for we in wg.edges_for_index(u):
# старое расстояние до этой вершины
dist_v: float = distances[we.v]
Затем исследуются все ребра, связанные с u. dist_v - это расстояние до всех известных вершин, соединенных ребром с u.
# старого расстояния не существует или найден более короткий путь
if dist_v is None or dist_v > we.weight + dist_u:
# изменить расстояние до этой Вершины
distances[we.v] = we.weight + dist_u
# заменить ребро на более короткий путь к этой вершине
path_dict[we.v] = we
# вскоре мы это проверим
pq.push(DijkstraNode(we.v, we.weight + dist_u))
Если мы обнаружили вершину, которая еще не была исследована (значение dist_v равно None), или нашли новый, более короткий путь к ней, то записываем новое кратчайшее расстояние до v и ребро, которое привело нас туда. Наконец, помещаем все вершины с новыми путями в очередь с приоритетом.
return distances, path_dict
Функция dijkstra() возвращает расстояния от корневой вершины до каждой вершины взвешенного графа, и path_dict, что позволяет определить кратчайшие пути к ним.
Теперь можно безопасно использовать алгоритм Дейкстры. Начнем с определения расстояния от Лос-Анджелеса до всех остальных MSA на графе. Тогда мы найдем кратчайший путь между Лос-Анджелесом и Бостоном. А в конце воспользуемся print_weighted_path(), чтобы красиво распечатать результат.
if __name__ == "__main__": city_graph2: WeightedGraph[str] = WeightedGraph(["Сиэтл", "Сан-Франциско", "Лос-Анджелес", "Риверсайд", "Феникс", "Чикаго", "Бостон", "Нью-Йорк", "Атланта", "Майами", "Даллас", "Хьюстон", "Детройт", "Филадельфия", "Вашингтон"]) city_graph2.add_edge_by_vertices("Сиэтл", "Чикаго", 1737) city_graph2.add_edge_by_vertices("Сиэтл", "Сан-Франциско", 678) city_graph2.add_edge_by_vertices("Сан-Франциско", "Риверсайд", 386) city_graph2.add_edge_by_vertices("Сан-Франциско", "Лос-Анджелес", 348) city_graph2.add_edge_by_vertices("Лос-Анджелес", "Риверсайд", 50) city_graph2.add_edge_by_vertices("Лос-Анджелес", "Феникс", 357) city_graph2.add_edge_by_vertices("Риверсайд", "Феникс", 307) city_graph2.add_edge_by_vertices("Риверсайд", "Чикаго", 1704) city_graph2.add_edge_by_vertices("Феникс", "Даллас", 887) city_graph2.add_edge_by_vertices("Феникс", "Хьюстон", 1015) city_graph2.add_edge_by_vertices("Даллас", "Чикаго", 805) city_graph2.add_edge_by_vertices("Даллас", "Атланта", 721) city_graph2.add_edge_by_vertices("Даллас", "Хьюстон", 225) city_graph2.add_edge_by_vertices("Хьюстон", "Атланта", 702) city_graph2.add_edge_by_vertices("Хьюстон", "Майами", 968) city_graph2.add_edge_by_vertices("Атланта", "Чикаго", 588) city_graph2.add_edge_by_vertices("Атланта", "Вашингтон", 543) city_graph2.add_edge_by_vertices("Атланта", "Майами", 604) city_graph2.add_edge_by_vertices("Майами", "Вашингтон", 923) city_graph2.add_edge_by_vertices("Чикаго", "Детройт", 238) city_graph2.add_edge_by_vertices("Детройт", "Бостон", 613) city_graph2.add_edge_by_vertices("Детройт", "Вашингтон", 396) city_graph2.add_edge_by_vertices("Детройт", "Нью-Йорк", 482) city_graph2.add_edge_by_vertices("Бостон", "Нью-Йорк", 190) city_graph2.add_edge_by_vertices("Нью-Йорк", "Филадельфия", 81) city_graph2.add_edge_by_vertices("Филадельфия", "Вашингтон", 123) distances, path_dict = dijkstra(city_graph2, "Лос-Анджелес") name_distance: Dict[str, Optional[int]] = distance_array_to_vertex_dict(city_graph2, distances) print("Расстояния от Лос-Анджелеса:") for key, value in name_distance.items(): print(f"{key} : {value}") print("") # пустая строка print("Кратчайший путь из Лос-Анджелеса в Бостон:") path: WeightedPath = path_dict_to_path(city_graph2.index_of("Лос-Анджелес"), city_graph2.index_of("Бостон"), path_dict) print_weighted_path(city_graph2, path)
Результат должен выглядеть примерно так:
Расстояния от Лос-Анджелеса: Сиэтл : 1026 Сан-Франциско : 348 Лос-Анджелес : 0 Риверсайд : 50 Феникс : 357 Чикаго : 1754 Бостон : 2605 Нью-Йорк : 2474 Атланта : 1965 Майами : 2340 Даллас : 1244 Хьюстон : 1372 Детройт : 1992 Филадельфия : 2511 Вашингтон : 2388 Кратчайший путь из Лос-Анджелеса в Бостон: Лос-Анджелес 50> Риверсайд Риверсайд 1704> Чикаго Чикаго 238> Детройт Детройт 613> Бостон Общая длина: 2605
Возможно, вы заметили, что у алгоритма Дейкстры есть некоторое сходство с алгоритмом Ярника. Оба они жадные, и при желании их можно реализовать, используя довольно похожий код. Другой алгоритм, похожий на алгоритм Дейкстры, - это А* из 30 шага. А* можно рассматривать как модификацию алгоритма Дейкстры. Добавьте эвристику и ограничьте алгоритм Дейкстры поиском только одного пункта назначения - и оба алгоритма окажутся одинаковыми.
Алгоритм Дейкстры предназначен для графов с положительными весами.
Графы с отрицательно взвешенными ребрами могут создать проблему и потребуют модификации или альтернативного алгоритма.
На следующем шаге мы подведем некоторые итоги.
