Алгоритм кратчайшего пути: Алгоритм Беллмана-Форда

задача о кратчайшем пути

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

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

Прежде чем продолжить, добавим свойство кратчайшего пути графа:Подпуть кратчайшего пути также является кратчайшим путем, математически описывается следующим образом: Ориентированный граф G=(V,E) ,Предполагать p=(v_0,v_1,...,v_k) из точки v_0 к точке v_k кратчайший путь к и 0≤i≤j≤k ,Предполагать $p_{ij}=(v_i,v_{i+1},...,v_j)$ для путисредняя точка v_i к точке v_j подпуть, затем $p_{ij}$ Это также кратчайший путь между этими двумя точками. От противного можно доказать, что:

Доказательство: если путьРазложен на, то есть $w(p)=w(p_{0i})+w(p_{ij})+w(p_{jk})$ . Предположим, естьприбытьболее короткий путь $p_{ij}'$ , $w(p_{ij}'<w(p_ij))$ . Тогда новый вес пути равен $w(p_{0i})+w(p_{ij}')+w(p_{jk}) < w(p)$ , что то же самое, чтократчайший путь противоречит.

Алгоритм Беллмана-Форда

Подобно алгоритму Дейкстры, алгоритм Беллмана-Форда также получает окончательное решение посредством непрерывных операций «релаксации». «Slack» — это процесс выполнения следующих действий: w(u,v) выражатьивеса между, d[v] значит из источникадо вершинырасстояние, если есть ребро e(u,v) , такой что: d[v] > d[u] + w(u,v) (то есть найден путь лучше текущего), затем обновить d[v] = d[u] + w(u,v) и обновите путь prev[v] = u . Видно, что каждое «расслабление» ближе к оптимальному решению. Алгоритм Дейкстры выбирает вершину с наименьшим расстоянием, необработанную в данный момент, каждый раз через приоритетную очередь и ослабляет необработанное ребро вершины. Алгоритм Беллмана-Форда просто ослабляет все ребра и выполняется многократно. |V|-1 Второсортный( |V| количество вершин), временная сложность O(|V||E|) . Видно, что количество релаксаций Беллмана-Форда намного больше, чем у Дейкстры, поэтому его временная сложность выше, чем у Дейкстры.

Псевдокод выглядит следующим образом:

function BellmanFord(list vertices, list edges, vertex source)
    // step 1 初始化, dist[v]表示源节点到顶点v的距离值，prev[v]表示顶点v的前驱顶点
    for each vertex v in vertices
        dist[v] = inf
        prev[v] = null

    dist[source] = 0

    // step 2 迭代松弛|V|-1次
    for i from 1 to size(vertices) -1 
        for each edge(u,v) with weight(u,v)  in edges
            if dist[u] + weight(u,v) < dist[v]
                dist[v] = dist[u] + weight(u,v)
                prev[v] = u
    
    // step 3 检查是否有负权回路
    for each edge(u,v) with weight(u,v) in edges
        if dist[u] + weight(u,v) < dist[v]
            error "检测到负权回路"

    return dist[], prev[]

Оптимизация алгоритма:В практических приложениях алгоритм Беллмана-Форда не требует итеративной релаксации. |V|-1 раз, теоретическая максимальная длина пути на графике равна |V|-1 , на самом деле часто меньше, чем это |V|-1 , то есть в |V|-1 Он сошёлся перед релаксацией следующей итерации, и был рассчитан кратчайший путь, поэтому в цикле можно установить суждение.Когда релаксация больше не выполняется в определённом цикле, это указывает на то, что ток сошёлся, и вы можете выйдите из шага 2 и перейдите к следующему шагу, чтобы проверить, есть ли цепь отрицательного веса.

Как понять этот алгоритм?Если предположить, что вершина не соединена с исходной вершиной, то есть ребра нет, то эта точка не будет расслаблена, расстояние не будет обновляться и оно по-прежнему бесконечно. Если вершина и исходная вершина соединены, то при отсутствии отрицательного весового цикла должен существовать кратчайший путь, этот кратчайший путь p=(v_0,v_1,...,v_k) исходная точкаприбытьлюбой кратчайший путь между (здесь v_0=s , v_k=v ). Какое максимальное количество ребер? Предположим, что граф имеет |V| вершина, то k≤|V|-1 . Во время первого раунда релаксации релаксированные ребра должны содержать ребра (v_0,v_1) , в сочетании с подпутью кратчайшего пути, упомянутого в начале статьи, также должен быть характером кратчайшего пути, v_1 Получен кратчайший путь, и во втором раунде релаксации релаксированное ребро должно содержать 边(v_1,v_2) , после этого расслабления, v_2 Также получен его кратчайший путь. И так далее, вВ релаксации колеса ослабленные ребра должны содержать ребра $(v_{k-1},v_k)$ ,после v_k Также получите его кратчайший путь. Другими словами, количество ребер, проходящих через кратчайший путь к исходной вершине, равновершины, наКогда колесо расслабится, это нужно подтвердить (найден кратчайший путь). Итак, сколько раундов нам нужно, чтобы расслабиться, максимум |V|-1 времени достаточно.

Математическое доказательство алгоритма может относиться к процессу доказательства в «Теории графов» или «Введении в алгоритмы».

См. реализацию кодаbellman_ford.cpp. Наконец, проанализируйте временную сложность, наихудший случай O(|V||E|) , это проще понять, в лучшем случае O(|E|) , достаточно релаксировать все ребра одновременно, и соответствующий порядок состоит в том, что порядок релаксации ребер в точности совпадает с порядком генерации дерева кратчайших путей.

Применение алгоритмов

Одним из приложений является протокол маршрутизации (протокол вектора расстояния), для которого реализован тестовый проект протокола маршрутизации, см. кодrouter. Реализован алгоритм маршрутизации через таблицу маршрутизации.

Наконец, приглашаем вас обратить внимание на публичный аккаунт WeChat: подумайте однажды, учитесь и развивайтесь вместе.