Введение в алгоритмы (MIT 6.006, лекция 15, лекция 16, лекция 17)

Каково определение кратчайшего пути?

Кратчайший путь — это путь p с наименьшим весом;
Определение пути: p=, v_0 ,..., v_k >где когда $0\leq i<k$ Когда есть( v_i , $v_{i+1}$ ) $\in$ E;
Вес пути: w(p)= $\Sigma{^{k-1}_{i=0}}w(v_i,v_{i+1})$ ;

Математическое представление плюсовых весов

Граф со взвешенным ребром: G(V,E,W) , W — это функция, которая действует на ребро для генерации действительного числа, то есть W(E)->R
Путь из вершины в себя :() означает из ()прибыть(), вес равен 0
Кратчайший путь между двумя вершинами:
$\delta(u,v)=\lbrace{^{min\lbrace w(p)\rbrace{\quad} u,v之间存在路径}_{\infty{\qquad}u,v之前不存在路径}}$

Связь между E и V E=O(). Для ориентированного графа предположим, что есть две вершины, v1, v2, и между ними всего 4 соединения и т. д.

Почему существуют отрицательные веса?

Например, лайки в социальных сетях можно рассматривать как положительные веса, а лайки — как отрицательные.

В чем проблема с ребрами с отрицательным весом?

Если есть ребро с отрицательным весом, исходное значение веса будет уменьшаться каждый раз, когда оно проходит через цикл, так что может быть получено любое доступное значение веса. Например, вес пути p= ~~равен 4, а вес пути p= ~~равен 3.~~~~

Какова общая идея алгоритма поиска кратчайшего пути?

d(v) представляет собой вес пути от исходной точки s до текущего узла v, $\pi[v]$ Представляет текущий лучший путь, предыдущий узел v, таким образом можно восстановить весь кратчайший путь.

Для петель без отрицательных весов

Инициализировать d[v] = $\infty$ , $\pi[u]$ =NIL,d[s]=0
Выберите ребро (u, v) каким-либо образом, выполните операцию Relax, чтобы обновить текущее значение пути от исходной точки до выбранной вершины и предыдущий узел выбранной вершины

Relax(u,v,w):
    select edge(u,v):
        if d[v]>d[u]+w(u,v):
            d[v]=d[u]+w(u,v)
            PI[v]=u
    until all edges have d[v] <= d[u]+w(u,v)

Будет ли соотношение один к одному во время операции релаксации? $\delta$ (s,v) еще меньшее значение?

По индукции предположим, что у нас есть d[u] $\geq$ $\delta$ (с, у). известно, что $\delta(s,v)$ Представляет кратчайший путь из s в v, тогда любая вершина u в v и кратчайший путь из источника s в u должны быть больше или равны $\delta(s,v)$ , то есть,

По предыдущим предположениям должно быть $\delta(s,v)\leq d[u]+w(u,v)=d[v]$ . Это показывает, что результат d[v], полученный на любой стадии промежуточного процесса, будет не более $\delta$ (s,v) еще меньше

Общая идея алгоритма кратчайшего пути Проблема 1: Неправильный выбор ребра приводит к экспоненциальной сложности

Постройте схему следующей структуры

Веса ребер основаны на $2^{n/2}$ путь назначения, пример 6 точек, приведенных на рисунке, если все отображаемые ребра (,) имеет вес $2^{n/2}$ , и уменьшать до 1 по очереди

Предположим, что исходная точка v_0

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

В этот момент расслабьтесь( v_4 , v_6 ), буду обновлять v_0 прибыть v_6 Длина пути 13

Расслабься( v_2

), буду обновлять v_0

прибыть

Длина пути 10

В связи с новым v_0

прибыть

длина пути становится короче, тогда ( v_0

) будет сокращено до 11

В это время ребро, которое может быть выбрано для выполнения Расслабления в первую очередь, это ( v_5

),Так(

) будет сокращено до 12

Снова сторона Relax ( v_4

),Так(

) будет сокращено до 11

Для случая с n вершинами:

Первый релакс( $v_{n-2}$ , $v_{n}$ ), так что д[] минус 1
Расслабься( $v_{n-4}$ , $v_{n-2}$ ), так что д[ $v_{n-2}$ ] минус 2
Тогда расслабься( $v_{n-2}$ , $v_{n-1}$ )а также( $v_{n-1}$ , $v_{n}$ ) такой, что d[] минус 1
Затем выполните Relax( $v_{n-2}$ , $v_{n}$ ), так что д[] минус 1

Можно обнаружить, что когда сторона Relax ( $v_{n-2}$ , $v_{n}$ ) при весе 1, так что вершина d ( v_n ) минус 1, когда сторона Relax ( $v_{n-4}$ , $v_{n-2}$ ) при весе 2, так что вершина d ( v_n ) минус 2, то есть из весов по 1,2,4,..., $2^{(n/2)-1}$ , $2^{(n/2)}$ Во время выполнения метода d( v_n ) общее количество раз, которое необходимо выполнить приведение, равно 1+2+4+...+ $2^{(n/2)}$ = $2^{(n/2)}-1$ , то есть количество выполнений экспоненциально

Общая идея алгоритма кратчайшего пути Задача 2: Петля с отрицательным весом

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

Как получить кратчайший путь от одной исходной точки до точки в ориентированном ациклическом графе (DAG)?

В представлении DAG просто нет колец, могут существовать отрицательные веса ребер

Топологически отсортируйте DAG, что гарантирует, что путь от u до v должен быть u до v
Найдите исходную точку, выполните операцию Relax для каждой проходящей через нее вершины в порядке расположения DAG слева направо и получите кратчайший путь от исходной точки ко всем вершинам.

Предполагая, что отсортированная топология выглядит следующим образом, для инициализации расстояние от каждой исходной точки до каждого узла считается равным $\infty$

Первый шаг — спуститься от исходной точки, найти все ее ребра и выполнить операцию Relax на ребрах.

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

Продолжайте движение вправо, чтобы выполнить Расслабление.

Продолжайте движение вправо, чтобы выполнить Расслабление.

Пока что выполнение завершено, вы видите кратчайший путь от исходной точки ко всем узлам, слева направо идут $\infty$ ,0,2,6,5,3

Как рассчитать кратчайший путь, если в графе есть цикл, но прохождение этого цикла не приводит к уменьшению веса?

Используйте алгоритм Дейкстры. Алгоритм псевдокода следующий:

Dijkstra(G,w,s): //G是图，w是权值，s是源点
    Initialize(G,s) // 初始化，设置d[s]=0,其它都是无穷，以及PI
    S <- {}    //已知最短路径的点的集合
    Q <- V[G]  //需要被处理的顶点，可以看做是一个最小优先级队列，根据d()值进行排序
    while Q is not empty: //只要还有没处理的节点
        u <- Extract-Min(Q) //从节点中找出一个最小的路径权重的节点，并从Q中移除
        S <- S U {u} //将找到的节点并到S中
        for each vertex v belong to Adj
            Relax(u,v,w) //对边的d()值进行更新

Пример выглядит следующим образом, выберите A в качестве исходной точки

Инициализируйте, расстояние от A до других узлов равно $\infty$ , а именно S={} , Q={A(0),B( $\infty$ ),C( $\infty$ ),D( $\infty$ ),E( $\infty$ )};
Получите минимальное значение в очереди, то есть сам A, в этот момент S={A(0)}, а затем выполните операцию Relax, то есть будет обнаружено, что вершины, которых может достичь A, это B и C, и значение в обновленной очереди равно Q = {B(10),C(3),D( $\infty$ ),E( $\infty$ )};
Получите минимальное значение в очереди, которое в данный момент равно C, S={A(0),C(3)}, выполните Relax на выбранном C, узлы C могут достичь B, D, E, и соответствующая очередь обновляется как: Q={B(7),D(11),E(5)};
Получите минимальное значение очереди, которое в данный момент равно E, S={A(0), C(3), E(5)}, выполните Relax на выбранном E, а узел, которого может достичь E, равен D , Значение D больше, поэтому обновления нет, Q={B(7), D(11)};
Получите минимальное значение очереди, на этот раз B, в это время S={A(0), C(3), E(5), B(7)}, B может добраться только до D, B до D полученное значение равно 9, чтобы быть меньше, обновите Q={D(9)}
Получите минимальное значение очереди, которое в данный момент равно D, и S={{A(0), C(3), E(5), B(7), D(9)}, и это конец.

Значения в скобках указывают расстояния пути

Временная сложность алгоритма Дейкстры

Все трудоемкие операции включают в себя:

Вставка всех вершин в приоритетную очередь занимает время $\theta(V)$ ;
Извлечение минимального значения из очереди приоритетов требует времени $\theta(V)$ ;
Операция Relax уменьшает значение d фронта, а время $\theta(E)$ ; Различные способы реализации приоритетных очередей занимают разное время.

Используйте массив. Извлеките минимальную стоимость: $\theta(V)$ , Relax уменьшает значение d $\theta(1)$ , обработайте все элементы в очереди, то время равно $\theta(V*V+E*1)$ = $\theta(V^2)$
Используйте минимальную кучу. Извлеките минимальную стоимость: $\theta(\lg V)$ , снизить стоимость ключей $\theta(\lg V)$ , обработайте все элементы в очереди, то время равно $\theta(V*\lg V+E*\lg V)$
Используя кучу Фибоначчи, извлеките минимальную стоимость: $\theta(\lg V)$ , снизить стоимость ключей $\theta(1)$ , может достигать $\theta(V*\lg V+E)$

Самое интуитивное ощущение от использования Dijkstra: следующий рисунок является примером:

Предполагая, что зеленая точка является исходной точкой, если вы используете веревку такой длины для соединения каждого узла, то возьмите зеленый шар и подвесьте его сверху вниз.Сумма прямых линий является кратчайшим расстоянием от источника точка на каждую точку.Например, зеленый цвет является исходной точкой, а кратчайшие расстояния до других точек равны 7, 12, 18, 22 соответственно (цвета фиолетовый, синий, желтый, красный)

Почему Дейкстра не может справиться с проблемой колец отрицательного веса?

Dikstra не будет смотреть на узлы, которые были обработаны, а будет обрабатывать только те узлы, которые не были просмотрены.Если все узлы, которые были обработаны, являются наименьшими значениями, и нет петли с отрицательным весом, не будет ситуации что делает путь меньше. Видеть:stackoverflow.com/questions/6…

Как решить проблему кратчайшего пути, если на пути от исходного узла к целевому узлу есть петля, и вес будет уменьшен?

Используйте алгоритм Беллмана-Форда.

Bellman-Ford(G,w,s):
    Initialuze(G,s)
    for i=1 to |V|-1:
        for each edge(u,v) belong to E:
            Relax(u,v,w)
    for each edge (u,v) belong to E:
        if d[v]>d[u]+w(u,v)
            report negative cycle exist

Что Беллман-Форд в конечном счете обеспечивает, так это то, что если нет колец отрицательного веса, кратчайший путь может быть возвращен (d[v]= $\delta(s,v)$ ), в противном случае просто определите кольца с отрицательными весами

Длительный анализ

Два цикла for, соответственно V и E, поэтому временная сложность равна O(VE).

Почему алгоритм Беллмана-Форда может вычислить минимальный путь при отсутствии циклов с отрицательным весом?

Нужно только доказать, что если кольца отрицательных весов нет, то через Беллмана-Форда d[v]= $\delta(s,v)$ .

Выберите кратчайший путь с наименьшим количеством ребер p=, v_1 ,..., v_k >, где v_0 для с, v_k =в. Если нет цикла с отрицательным весом, то p — простой путь, а значит, k $\leq$ |В|-1.

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

Когда выполняется первый цикл, ребра извлекаются ( v_0 , v_1 ) для Relax, то есть $\delta(s,v_1)=d[v_1]$ Выполняется вторая петля, и полученный край ( v_1 , v_2 ) для Relax, то есть $\delta(s,v_2)=d[v_2]$
Тогда после k раундов циклов мы имеем $\delta(s,v_k)=d[v_k]$ , то есть после |V|-1 циклов обращения каждая вершина, достижимая из исходной точки, вычисляет кратчайший путь

Простой путь: Помимо начальной и конечной точек, другие вершины не будут повторяться. Для простых путей p=,,...,>С точки зрения k>=|V|, тогда общее количество вершин на пути равно |V|+1, но на самом деле вершин только |V|, тогда должно быть дублирующее ребро, так что не- отправная точка и конечная точка повторяются, То есть он не легкий путь.

Почему алгоритм Беллмана-Форда обнаруживает петли с отрицательным весом?

После |V|-1 раундов обращения, если все еще есть ребро, которое может Расслабиться, то текущий кратчайший путь из s в v не является простым путем, так как все узлы были просмотрены, и на этом должны быть повторяющиеся узлы. время. , то есть существует отрицательно взвешенное кольцо

Если на пути есть цикл, и все значения весов являются отрицательными весами, можно ли получить самый длинный путь с помощью алгоритма Беллмана-Форда?

Нет, потому что Беллман-Форд выдает исключение только при наличии кольца с отрицательным весом и не вычисляет путь.На самом деле это проблема NP, то есть затраченное время находится на экспоненциальном уровне или выше.

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