|
|
Алгоритм Дейкстры
Известнo, что все
цены неотрицательны. Найти наименьшую стоимость проезда 1->i для
всех i=1..n за время
O(n2).
В
процессе работы алгоритма некоторые города будут выделенными (в
начале - только город 1, в конце - все). При
этом:
для каждого выделенного
города i хранится наименьшая стоимость пути 1->i; при этом
известно, что минимум достигается на пути, проходящем только через
выделенные города;
для каждого
невыделенного города i хранится наименьшая стоимость пути 1->i, в
котором в качестве промежуточных используются только выделенные
города.
Множество выделенных
городов расширяется на основании следующего замечания: если среди
всех невыделенных городов взять тот, для которого хранимое число
минимально, то это число является истинной наименьшей стоимостью. В
самом деле, пусть есть более короткий путь. Рассмотрим первый
невыделенный город на этом пути - уже до него путь длиннее! (Здесь
существенна неотрицательность
цен.)
Добавив выбранный город к
выделенным, мы должны скорректировать информацию, хранимую для
невыделенных городов. При этом достаточно учесть лишь пути, в
которых новый город является последним пунктом пересадки, а это
легко сделать, так как минимальную стоимость проезда в новый город
мы уже знаем.
При самом
бесхитростном способе хранения множества выделенных городов (в
булевском векторе) добавление одного города к числу выделенных
требует времени O(n).
Схема алгоритма Дейкстры
Алгоритм использует три массива из N (= числу вершин сети) чисел
каждый. Первый массив S содержит метки с двумя значения: 0 (вершина
еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B
содержит расстояния - текущие кратчайшие рас- стояния от до
соответствующей вершины; третий массив с содержит номера вершин -
k-й элемент С[k] есть номер предпоследней вершины на текущем
кратчайшем пути из Vi в Vk. Матрица расстояний A[i,k] задает длины
дуге A[i,k]; если такой дуги нет, то A[i,k] присваивается большое
число Б, равное "машинной бесконечности".
1 (инициализация). В цикле от 1 до N заполнить нулями массив
S; заполнить числом i массив C; перенести i-ю строку матрицы
A в массив B,
S[i]:=1; C[i]:=0 (i - номер стартовой вершины)
2 (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для
которых S[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k]
Затем выполняются следующие операции:
S[j]:=1;
если B[k] > B[j]+A[j,k], то (B[k]:=B[j]+A[j,k]; C[k]:=j)
(Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk).
(Если все S[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь
надо) перечислить вершины, входящие в кратчайший путь).
3 (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке
следующей процедурой:)
3.1. z:=C[k];
3.2. Выдать z;
3.3. z:=C[z]. Если z = О, то конец,
иначе перейти к 3.2.
Для выполнения алгоритма нужно N раз просмотреть массив B из N
элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность:
O(n2). Отыскании кратчайшего пути
имеет естественную интерпретацию в терминах матриц. Пусть A -
матрица цен одной аваиакомпании, а B - матрица цен другой. (Мы
считаем, что диагональные элементы матриц равны 0.) Пусть мы хотим
лететь с одной пересадкой, причем сначала самолетом компании A, а
затем - компании B. Сколько нам придется заплатить, чтобы попасть из
города i в город j?
Можно
доказать, что эта матрица вычисляется по обычной формуле для
произведения матриц, только вместо суммы надо брать минимум, а
вместо умножения -
сумму.
Обычное (не
модифицированное) умножение матриц тоже может оказаться полезным,
только матрицы должны быть другие. Пусть есть не все рейсы (как в
следующем разделе), а только некоторые, a[i,j] равно 1, если рейс
есть, и 0, если рейса нет. Возведем матрицу a (обычным образом) в
степень k и посмотрим на ее i-j-ый
элемент.
Он равен числу
различных способов попасть из i в j за k рейсов.
Случай, когда есть не все рейсы, можно свести к исходному, введя
фиктивные рейсы с бесконечно большой (или достаточно большой)
стоимостью.
|
|
