def bellman_ford(graph, start): distances = {node: float("infinity") for node in graph} distances[start] = 0 for _ in range(len(graph) - 1): # V-1 итераций for node in graph: for neighbor, weight in graph[node].items(): if distances[node] + weight < distances[neighbor]: distances[neighbor] = distances[node] + weight return distances Сложность Беллмана–Форда выше — O(V·E), но он способен обнаруживать отрицательные циклы и, соответственно, определять, что задача не имеет решения. Сравним два подхода: - Дейкстра: работает только с неотрицательными весами, быстрее (O((V+E) log V)). - Беллман–Форд: работает с любыми весами, медленнее (O(V·E)), может обнаруживать отрицательные циклы. В реальной жизни алгоритм Дейкстра широко применяется. Например, в GPS-навигаторах (Google Maps, Яндекс.Карты) города или перекрёстки — это вершины, дороги — рёбра, а весом может быть время в пути. Алгоритм находит маршрут с минимальным временем. В интернете протоколы маршрутизации, такие как OSPF, используют алгоритм Дейкстры для определения кратчайшего пути передачи пакетов данных (вершины — роутеры, рёбра — каналы связи, вес — задержка или пропускная способность). В игровых движках NPC (неигровые персонажи) находят путь по карте с препятствиями. В системах поиска авиабилетов вершинами выступают аэропорты, рёбрами — рейсы, а весом — стоимость или время, что позволяет находить самые дешёвые или быстрые маршруты с пересадками. #algorithm