Когда дело доходит до поиска кратчайшего пути в графе, на ум часто приходят два популярных алгоритма: алгоритм Беллмана-Форда и алгоритм Дейкстры. В этой статье мы рассмотрим оба алгоритма, сравнивая их подходы, подчеркивая их различия и предоставляя примеры кода. Итак, приступим!

Алгоритм Беллмана-Форда.
Алгоритм Беллмана-Форда представляет собой алгоритм поиска кратчайшего пути с одним источником, который работает как с положительными, так и с отрицательными весами ребер. Это алгоритм, основанный на динамическом программировании, который вычисляет кратчайший путь от заданной исходной вершины ко всем остальным вершинам графа.

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

Вот пример реализации алгоритма Беллмана-Форда на Python:

def bellman_ford(graph, source):
    # Step 1: Initialize distances
    distances = {v: float('inf') for v in graph}
    distances[source] = 0
    # Step 2: Relax edges repeatedly
    for _ in range(len(graph) - 1):
        for u, v, weight in graph:
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
    # Step 3: Check for negative cycles
    for u, v, weight in graph:
        if distances[u] + weight < distances[v]:
            raise ValueError("Graph contains a negative cycle.")
    return distances

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

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

Вот пример реализации алгоритма Дейкстры на Python:

import heapq
def dijkstra(graph, source):
    distances = {v: float('inf') for v in graph}
    distances[source] = 0
    heap = [(0, source)]
    while heap:
        current_distance, current_vertex = heapq.heappop(heap)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return distances

Сравнение и
Алгоритмы Беллмана-Форда и Дейкстры имеют свои сильные и слабые стороны. Алгоритм Беллмана-Форда может обрабатывать графы с отрицательными весами ребер и обнаруживать отрицательные циклы, но его временная сложность равна O(V E), где V — количество вершин, а E — количество ребер. С другой стороны, алгоритм Дейкстры имеет временную сложность O((V + E)log V) и более эффективен для графов с неотрицательными весами ребер.

Подводя итог, если вы имеете дело с графом, который может содержать отрицательные веса ребер или отрицательные циклы, алгоритм Беллмана-Форда является подходящим выбором. Однако если вы работаете с графом, имеющим только неотрицательные веса ребер, алгоритм Дейкстры обычно более эффективен.