Поиск пути наименьшей длины

Слайд 2

Поиск расстояния между всеми парами вершин. Алгоритм Уоршалла-Флойда Вход: матрица С

Поиск расстояния между всеми парами вершин. Алгоритм Уоршалла-Флойда

Вход: матрица С

длин дуг.
Выход: матрица Т длин путей и матрица H самих путей.
for г from 1 to p do
for j from 1 to p do
T[i,j] = C[i,j] { инициализация }
if C[i,j] = ∞ then H[i, j] = 0 { нет дуги из i в j }
else H[i,j]: =j
end
end
Слайд 3

for i from 1 to p do for j from 1

for i from 1 to p do
for j from

1 to p do
for k from 1 to p do
if i≠ j & T[j, i] ≠ ∞ & i ≠k & T[i,k] ≠ ∞ &
(T[j, k] = ∞ V T[j, k] > T[j,i] + T[i,k])
then H[j,k] = H[j, i] { запомнить новый путь }
T[j,k]: = T[j, i] + T[i, k] { и его длину }
end
end
for j from 1 to p do
if T[j,j]<0 then stop { нет решения}
end
end
Слайд 4

Слайд 5

Пусть G = – взвешенный орграф без петель. Поиск пути наименьшей

Пусть G = – взвешенный орграф без петель.
Поиск пути наименьшей длины

между вершинами s (начало) и t(конец).
Алгоритм Дейкстры
Вход: орграф G(V,E), заданный матрицей длин дуг С pхp
s и t — вершины графа.
Выход: векторы T и H длиной p.
Если вершина v лежит на кратчайшем пути от s к t,
то T[v] — длина кратчайшего пути от s к v;
H[v] — вершина, непосредственно предшествующая v на кратчайшем пути.
for v from 1 to p do
T[v] = ∞ { кратчайший путь неизвестен }
X [v] = 0 { все вершины не отмечены }
end
Слайд 6

H[s]: = 0; T[s]: = 0; X [s] = 1 v

H[s]: = 0; T[s]: = 0; X [s] = 1
v

= s { текущая вершина }
М: { обновление пометок }
for u in Г(v) do
if X[u] = 0 & T[u] > T[v] + C[v, u]
then T[u]=T[v]+C[v,u] { найден более короткий путь }
H[u] = v { запоминаем его }
end
m = ∞; v=0 { поиск конца кратчайшего пути }
for u from 1 to p do
if X[u] = 0 & T[u] < m
then v= u; m: = T[u]
end
if v = 0 then
stop { нет пути из s в t }
if v = t then stop { найден кратчайший путь из s в t }
X[v] = 1 { найден кратчайший путь из s в v }
goto M
Слайд 7

Пример:


Пример:

Слайд 8

Слайд 9

Слайд 10

Слайд 11