Содержание
- 2. Поиск расстояния между всеми парами вершин. Алгоритм Уоршалла-Флойда Вход: матрица С длин дуг. Выход: матрица Т
- 3. for i from 1 to p do for j from 1 to p do for k
- 5. Пусть G = – взвешенный орграф без петель. Поиск пути наименьшей длины между вершинами s (начало)
- 6. H[s]: = 0; T[s]: = 0; X [s] = 1 v = s { текущая вершина
- 7. Пример:
- 13. Скачать презентацию
Слайд 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
Выход: матрица Т длин путей и матрица 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
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
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
Алгоритм Дейкстры
Вход: орграф 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
М: { обновление пометок }
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