E032. Нахождение кратчайших путей от заданной вершины до всех остальных вершин 算法ом Дейкстры

Источник: e-maxx.ru/algo, страница PDF 101.

Постановка задачи

Дан ориентированный или неориентированный взвешенный 图 с

vertexми и

рёбрами. Веса всех

рёбер неотрицательны. Указана некоторая стартовая vertex

. it is required find длины кратчайших путей из вершины

во все остальные вершины, а также предоставить способ вывода самих кратчайших путей. Эта 题目 называется "задачей о кратчайших путях с единственным источником" (single-source shortest paths problem).

算法

Здесь описывается 算法, который предложил датский исследователь Дейкстра (Dijkstra) в 1959 г.

Заведём 数组

, в котором для каждой вершины

будем хранить текущую длину

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

в

. Изначально

, а для всех остальных вершин эта длина равна бесконечности (при реализации на компьютере обычно в качестве бесконечности выбирают просто достаточно большое number, заведомо большее возможной длины пути):

Кроме того, для каждой вершины

будем хранить, помечена она ещё или нет, т.е. заведём булевский 数组 . Изначально все вершины не помечены, т.е.

Сам Dijkstra's algorithm состоит из

итераций. На очередной итерации выбирается vertex

с

наименьшей величиной

среди ещё не помеченных, т.е.: (Понятно, что на первой итерации выбрана будет стартовая vertex

.)

Выбранная таким образом vertex

отмечается помеченной. Далее, на текущей итерации, из вершины

производятся релаксации: просматриваются все рёбра

, исходящие из вершины

, и для каждой

такой вершины

算法 пытается улучшить значение

. Пусть длина текущего ребра равна

, тогда в

виде кода релаксация выглядит как: На этом текущая итерация заканчивается, 算法 переходит к следующей итерации (снова выбирается vertex

с наименьшей величиной

, из неё производятся релаксации, и т.д.). При этом в конце концов, после

итераций,

все вершины 图а станут помеченными, и 算法 свою работу завершает. Утверждается, что найденные

значения

и есть искомые длины кратчайших путей из

в

. Стоит заметить, что, если не все вершины 图а достижимы из вершины

, то значения

для них так и

останутся бесконечными. Понятно, что несколько последних итераций 算法а будут как раз выбирать эти вершины, но никакой полезной работы производить эти итерации не будут (поскольку бесконечное расстояние не сможет прорелаксировать другие, даже тоже бесконечные расстояния). Поэтому 算法 можно сразу останавливать, как только в качестве выбранной вершины берётся vertex с бесконечным расстоянием. Восстановление путей. Разумеется, обычно нужно знать не только длины кратчайших путей, но и получить сами пути. Покажем, как сохранить информацию, достаточную для последующего восстановления кратчайшего пути из до любой вершины. Для этого достаточно так называемого 数组а предков: 数组а

, в котором для

каждой вершины

хранится номер вершины

, являющейся предпоследней в кратчайшем пути до вершины

. Здесь используется тот факт, что если мы возьмём 最短路径 до какой-то вершины

, а затем удалим из

этого пути последнюю вершину, то получится путь, оканчивающийся некоторой вершиной

, и этот путь

будет кратчайшим для вершины

. Итак, если мы будем обладать этим 数组ом предков, то 最短路径 можно будет восстановить по нему, просто каждый раз беря предка от текущей вершины, пока мы не придём в

стартовую вершину

— так мы получим искомый 最短路径, но записанный в обратном порядке. Итак,

最短路径

до вершины

равен: Осталось понять, как строить этот 数组 предков. Однако это делается очень просто: при каждой успешной релаксации,

т.е. когда из выбранной вершины

происходит улучшение расстояния до некоторой вершины

, мы записываем,

что предком вершины

является vertex

:

证明

Основное утверждение, на котором основана корректность 算法а Дейкстры, следующее. Утверждается,

что после того как какая-либо vertex

становится помеченной, текущее расстояние до неё

уже

является кратчайшим, и, соответственно, больше меняться не будет. 证明 будем производить по индукции. Для первой итерации справедливость его очевидна —

для вершины

имеем

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

не нарушается после выполнения текущей итерации. Пусть

— vertex, выбранная на текущей итерации, т.е.

vertex, которую 算法 собирается пометить. Докажем, что

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

неё (обозначим эту длину через

).

Рассмотрим 最短路径

до вершины

. Понятно, этот путь можно разбить на два пути:

, состоящий только

из помеченных вершин (как минимум стартовая vertex

будет в этом пути), и остальная часть пути

(она тоже

может включать помеченные вершины, но начинается обязательно с непомеченной). Обозначим через

первую

вершину пути

, а через

— последнюю вершины пути

.

Докажем сначала наше утверждение для вершины

, т.е. докажем равенство

. Однако это

практически очевидно: ведь на одной из предыдущих итераций мы выбирали вершину

и выполняли релаксацию из

неё. Поскольку (в силу самого выбора вершины

) 最短路径 до

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

плюс

edge

, то при выполнении релаксации из

величина

действительно установится в требуемое значение. Вследствие неотрицательности стоимостей рёбер длина кратчайшего пути

(а она по только что доказанному

равна

) не превосходит длины

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

. given, что

(ведь

Dijkstra's algorithm не мог find более короткого пути, чем это вообще возможно), в итоге получаем соотношения:

С другой стороны, поскольку и

, и

— вершины непомеченные, то так как на текущей итерации была выбрана

именно vertex

, а не vertex

, то получаем другое неравенство:

Из этих двух неравенств заключаем равенство

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

实现

Итак, Dijkstra's algorithm представляет собой

итераций, на каждой из которых выбирается непомеченная vertex

с наименьшей величиной

, эта vertex помечается, и затем просматриваются все рёбра, исходящие из данной вершины, и вдоль каждого ребра делается попытка улучшить значение на другом конце ребра. 运行时间 算法а складывается из:

●

раз поиск вершины с наименьшей величиной

среди всех непомеченных вершин, т.е. среди

вершин

●

раз производится попытка релаксаций

При простейшей реализации этих операций на поиск вершины будет затрачиваться

операций, а на

одну релаксацию —

операций, и итоговая Asymptotic complexity 算法а составляет: 实现:

const int INF = 1000000000;

int main() {

int n;

... чтение n ...

vector < vector < pair<int,int> > > g (n);

... чтение 图а ...

int s = ...; // стартовая vertex

vector<int> d (n, INF), p (n);

d[s] = 0;

vector<char> u (n);

for (int i=0; i<n; ++i) {

int v = -1;

for (int j=0; j<n; ++j)

if (!u[j] && (v == -1 || d[j] < d[v]))

v = j;

if (d[v] == INF)

break;

u[v] = true;

for (size_t j=0; j<g[v].size(); ++j) {

int to = g[v][j].first,

len = g[v][j].second;

if (d[v] + len < d[to]) {

d[to] = d[v] + len;

p[to] = v;

} } } }

Здесь 图

хранится в виде списков смежности: для каждой вершины

список

содержит список рёбер,

исходящих из этой вершины, т.е. список пар

, где первый element пары — vertex, в

которую ведёт edge, а второй element — вес ребра.

После чтения заводятся 数组ы расстояний

, меток

и предков

. Затем выполняются

итераций. На

каждой итерации сначала находится vertex

, имеющая наименьшее расстояние

среди непомеченных вершин.

Если расстояние до выбранной вершины

оказывается равным бесконечности, то 算法 останавливается. Иначе vertex помечается как помеченная, и просматриваются все рёбра, исходящие из данной вершины, и вдоль каждого ребра выполняются релаксации. Если релаксация успешна (т.е. расстояние

меняется),

то пересчитывается расстояние

и сохраняется предок

.

После выполнения всех итераций в 数组е

оказываются длины кратчайших путей до всех вершин, а в 数组е

— предки всех вершин (кроме стартовой

). Восстановить путь до любой вершины

можно следующим образом:

vector<int> path;

for (int v=t; v!=s; v=p[v])

path.push_back (v);

path.push_back (s);

reverse (path.begin(), path.end());

References

● Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. 算法ы: Построение и

анализ [2005]

● Edsger Dijkstra. A note on two problems in connexion with graphs [1959]

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    const int INF = 1000000000;
    int main() {
            int n;
            ... чтение n ...
            vector < vector < pair<int,int> > > g (n);
            ... чтение графа ...
            int s = ...; // стартовая вершина
            List<int> d (n, INF),  p (n);
            d[s] = 0;
            List<char> u (n);
            for (int i=0; i<n; ++i) {
                    int v = -1;
                    for (int j=0; j<n; ++j)
                            if (!u[j] && (v == -1 || d[j] < d[v]))
                                    v = j;
                    if (d[v] == INF)
                            break;
                    u[v] = true;
                    for (size_t j=0; j<g[v].size(); ++j) {
                            int to = g[v][j].first,
                                    len = g[v][j].second;
                            if (d[v] + len < d[to]) {
                                    d[to] = d[v] + len;
                                    p[to] = v;
                            }
                    }
            }
    }
    List<int> path;
    for (int v=t; v!=s; v=p[v])
            path.push_back (v);
    path.push_back (s);
    reverse (path.begin(), path.end());
}

const int INF = 1000000000;
int main() {
        int n;
        ... чтение n ...
        vector < vector < pair<int,int> > > g (n);
        ... чтение графа ...
        int s = ...; // стартовая вершина
        vector<int> d (n, INF),  p (n);
        d[s] = 0;
        vector<char> u (n);
        for (int i=0; i<n; ++i) {
                int v = -1;
                for (int j=0; j<n; ++j)
                        if (!u[j] && (v == -1 || d[j] < d[v]))
                                v = j;
                if (d[v] == INF)
                        break;
                u[v] = true;
                for (size_t j=0; j<g[v].size(); ++j) {
                        int to = g[v][j].first,
                                len = g[v][j].second;
                        if (d[v] + len < d[to]) {
                                d[to] = d[v] + len;
                                p[to] = v;
                        }
                }
        }
}
vector<int> path;
for (int v=t; v!=s; v=p[v])
        path.push_back (v);
path.push_back (s);
reverse (path.begin(), path.end());

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    const int INF = 1000000000;
    int main() {
            int n;
            ... чтение n ...
            vector < vector < pair<int,int> > > g (n);
            ... чтение графа ...
            int s = ...; // стартовая вершина
            ArrayList<Integer> d (n, INF),  p (n);
            d[s] = 0;
            ArrayList<Character> u (n);
            for (int i=0; i<n; ++i) {
                    int v = -1;
                    for (int j=0; j<n; ++j)
                            if (!u[j] && (v == -1 || d[j] < d[v]))
                                    v = j;
                    if (d[v] == INF)
                            break;
                    u[v] = true;
                    for (size_t j=0; j<g[v].size(); ++j) {
                            int to = g[v][j].first,
                                    len = g[v][j].second;
                            if (d[v] + len < d[to]) {
                                    d[to] = d[v] + len;
                                    p[to] = v;
                            }
                    }
            }
    }
    ArrayList<Integer> path;
    for (int v=t; v!=s; v=p[v])
            path.push_back (v);
    path.push_back (s);
    reverse (path.begin(), path.end());
}