Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 6. Графы. Поиск кратчайшего пути. Алгоритм Дейкстры.

Пусть дан взвешенный граф с N вершинами и M ребрами. Требуется найти кратчайшие расстояния от данной вершины до всех остальных. Эта задача может быть решена с помощью алгоритма Дейкстры.

Заметим, что алгоритм Дейкстры работает только в графах, веса ребер которых неотрицательны.

Обозначим начальную вершину X.

Проследим за ходом работы этого алгоритма. В каждый момент времени у нас будут 3 множества вершин:
  1) те вершины, до которых мы нашли кратчайшее расстояние
  2) вершины, до которых мы знаем текущее кратчайшее расстояние, за которое мы до этой вершины можем дойти, но еще не знаем, является ли оно минимальным в целом.
  3) вершины, ни одного пути до которых (и ни одного расстояния соответственно) нам не известно.

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

На каждом шаге мы будем совершать следующие действия:

• Найдем минимум из расстояний от начальной вершины до вершин из второго множества и запомним вершину второго множества, на которой этот минимум достигается (обозначим ее Р)
• Перенесем вершину Р из второго множества в первое
• Переберем всех соседей вершины Р. Обозначим текущего соседа, с которым мы работаем, U.
Заметим, что в данный момент мы нашли путь из вершины Х в вершину U: это путь из вершины Х в вершину Р, дополненный ребром (Р,U).
1. Если U лежит в третьем множестве, то мы должны перенести вершину U во второе множество, а расстояние до него посчитать как длину пути, описанного выше.
2. Если U лежит во втором множестве, то сравнив длину нового найденного нами пути и ранее известное расстояние до этой вершины, запишем вместо ранее известного расстояния минимальное из них
3. Если сосед U лежит в первом множестве, то с ним нам делать ничего не нужно, ведь до него наилучшее расстояние уже найдено, и с помощью любых дополнительных проверок улучшить его не удастся.

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

Хранить множества лучше всего с помощью массива из N элементов, где соответствующий элемент равен 0, если вершина лежит в первом множестве, 1 - если во втором и 2 - если в третьем .

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