Математика / Курсовая работа: Алгоритм Дейкстры

Курсовая работа: Алгоритм Дейкстры

Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших путей. Останов.

Если некоторые пометки являются временными, перейти к шагу 2.

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

Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S₁ – множество вершин с этими пометками, а S₂ – множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l(x_i ) дает кратчайший путь от sк x_i , проходящий полностью по вершинам множества S₁ . (Так как при каждой итерации во множество S₁ включается только одна вершина, то обновление пометки l(x_i ) требует только одного сравнения на шаге 2.)

Пусть кратчайший путь от s к x_i * не проходит целиком по S₁ и содержит по крайней мере одну вершину из S₂ , и пусть x_j S₂ – первая такая вершина в этом пути. Так как по предположению c_ij неотрицательны, то часть пути от x_j к x_i * должна иметь неотрицательный вес и. Это, однако, противоречит утверждению, что l(x_i *) – наименьшая временная пометка, и, следовательно, кратчайший путь к x_i * проходит полностью по вершинам множества S₁ , и поэтому l(x_i *) является его длиной.

Так как вначале множество S₁ равно (s) при каждой итерации к S₁ добавляется x_i *, то предположение, что l(x_i *) равно длине кратчайшего путиx_i S₁ , выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.

Если требуется найти кратчайшие пути между s и всеми другими вершинами полного связного графа с n вершинами, то в процессе работы алгоритма выполняются операций сложения и сравнения на шаге 2 и еще операций сравнения на шаге 3. Кроме того, при осуществлении шагов 2 и 3 необходимо определить, какие вершины временные, а для этого нужно еще операций сравнения. Эти величины являются верхними границами для числа операций, необходимых при отыскании кратчайшего пути между заданными вершинами s и t. Они действительно достигаются, если окажется, что вершина t будет последней вершиной, получившей постоянную пометку.

Как только длины кратчайших путей от s будут найдены (они будут заключительными значениями пометок вершин), сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения (*). Так как вершина x_i ' непосредственно предшествует вершине x_i в кратчайшем пути от s к x_i , то для любой вершины x_i соответствующую вершину x_i ' можно найти как одну из оставшихся вершин, для которой

''. (*)

Если кратчайший путь от s до любой вершины x_i является единственным, то дуги (x_i ', x_i ) этого кратчайшего пути образуют ориентированное дерево с корнем s. Если существует несколько «кратчайших» путей от s к какой-либо другой вершине, то при некоторой фиксированной вершине x_i ' соотношение (*) будет выполняться для более чем одной вершины x_i . В этом случае выбор может быть либо произвольным (если нужен какой-то один кратчайший путь между s и x_i ), либо таким, что рассматриваются все дуги (x_i ', x_i ), входящие в какой-либо из кратчайших путей и при этом совокупность всех таких дуг образует не ориентированное дерево, а общий граф, называемый базой относительно s или кратко – s-базой .

2.2 Задачи с методическим описанием

Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа

Неориентированное ребро будем рассматривать как пару противоположно ориентированных дуг равного веса. Воспользуемся алгоритмом Дейкстры. Постоянные пометки будем снабжать знаком +, остальные пометки рассматриваются как временные.