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

📟 Прилетело из @solidityset