Главная Обратная связь

Дисциплины:






Теоретическое описание метода Дейкстры



Методические указания к курсовой работе по дисциплине

«Дискретная математика»

 

СОДЕРЖАНИЕ

1. Поиск кратчайшего пути в орграфе методом Дейкстры . . . . . . . . . .
  1.1. Теоретическое описание метода Дейкстры. . . . . . . . . . . . . . .
  1.2. Пример решения задачи методом Дейкстры. . . . . . . . . . . . . .
2. Поиск кратчайших путей между всеми вершинами графа методом Флойда. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  2.1. Теоретическое описание метода Флойда. . . . . . . . . . . . . . . . .
  2.2. Пример решения задачи методом Флойда. . . . . . . . . . . . . . . .
3. Задание на курсовую работу. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Приложение 1. Образец оформления титульного листа. . . . . . . . . . . . .

Поиск кратчайшего пути в орграфе методом Дейкстры

Теоретическое описание метода Дейкстры

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

Граф задан матрицей весов дуг размера .

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

Начальную и конечную вершины обозначим соответственно и . — маршрут минимального веса будем называть кратчайшим -маршрутом.

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

Значения меток определяют верхние границы длин кратчайших маршрутов от начальной вершины до произвольной вершины .

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

Постоянные метки не меняют своего значения до конца алгоритма.

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



Кроме того, для определения последовательности вершин в кратчайшем маршруте можно использовать следующую рекуррентную процедуру:

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

.

На подготовительном (нулевом) шаге начальной вершине присваивается окончательная метка , а всем остальным вершинам ( ) временные метки .

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

Вершины имеют временные метки. Для них производится пересчет значений меток в соответствии с формулой

,

где -вeca дуг, соединяющих вершину , получившую окончательную метку на предыдущем шаге, с ее «детьми» .

Метки остальных вершин остаются без изменений.

Среди всех вершин с временными метками находится вершина , имеющая минимальную метку

.

На каждом шаге определяется множество вершин , получивших окончательные метки, – множество вершин, имеющих временные метки.

Метка вершины считается постоянной и принимается .

Тогда

; .

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

Метка — вес кратчайшего -маршрута.

Этот маршрут определяется с помощью меток :

,

где для любой вершины графа.

Формальное описание алгоритма имеет вид.

1. Положить и считать эту метку постоянной. Положить для всех , ; ; .

2. Для всех с временными метками пересчитать метки по формуле:

.

3. Множество вершин с временными метками .

Среди вершин с временными метками найти такую , что

.

Считать метку постоянной.

Присвоить ; ; .

4. Если , то перейти к п. 5.

– вес кратчайшего маршрута. Иначе положить и перейти к п.2

5. Кратчайший маршрут определяется метками :

.

Конец.

 

 





sdamzavas.net - 2017 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...