Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дейкстры

Постановка задачи:

Пусть задан орграф G=(V,E) с заданными положительными длинами ребер. Найти длину кратчайшего пути (и сам путь), соединяющий 2 произвольные фиксированные вершины s (начало) и t (конец).

Алгоритм Дейкстры:

1. В начале алгоритма все вершины не окрашены. Каждой вершине V во время выполнения алгоритма ставиться в соответствие либо L(V) – длина кратчайшего пути включающего только окрашенные вершины, L'(V) – временная метка, которая становиться равной L(V) в момент когда V окрашивается.

Полагаем что L(S)=0, L’(V)=∞, S≠V. Окрашиваем вершину S.

2. Для каждой неокрашенной вершины и соседней с последней из окрашенных вершинV пересчитываем L(U)=min{L’(U), L(V)+L(V,U)}, где L(V,U) – длина дуги между V и U.

Если L'(U)=∞ для любой неокрашенной вершины U, то алгоритм следует закончить. Так как в исходной сети не существует пути из S в неокрашенные вершины, в том числе и в Е. в противном случае находим вершины R, для которой L'(R) =L’(U), после чего К окрашиваем и вносим в корневое дерево дугу (V,R). Вершина R становится последней из окрашенных вершин.

3. В момент, когда вершина T становится окрашенной, находим кратчайший путь, соединяющий S и T, состоящий из окрашенных дуг.

3

4 7

3 2

L(S)=0	L(C)=3(S->C)	L(A)=4 (S->A)	L(D)=6(S->C->D)	L’(b)=7(S->B)	L(T)=8 (S->C->D->T)
L’(A)=4 L’(B)=7 L’(C)=3	L’(D)=3+3=6	L’(B)=7 L’(D)=6	L’(T)=8	L’(T)=9

Дата добавления: 2015-10-13