Читать курсовая по математике: "Алгоритм Дейкстры" Страница 3

(Назад) (Cкачать работу)

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

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

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

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

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

Похожие работы