ВУЗ:
Составители:
Рубрика:
81
Рассмотрим другой алгоритм для нахождения кратчайших путей во
взвешенном ориентированном графе. Он основан на методе динамическо-
го программирования.
Иллюстративный взвешенный граф представлен на рис. 45.
Предполагается, что все дуги этого графа ориентированы слева на-
право, но для простоты изображения стрелки опущены. Число над дугой
обозначает её длину.
Задача состоит в нахождении кратчайшего пути из любой вершины
v
i
до вершины v
k
.
0
0
1
3
ν
0
ν
1
*
ν
2
ν
3
ν
4
ν
5
ν
6
ν
7
ν
8
ν
9
ν
10
ν
11
1
3
3
4
3
4
4
6
1
0
0
1
3
ν
0
ν
1
ν
2
ν
3
ν
4
ν
5
*
ν
6
ν
7
ν
8
ν
9
ν
10
ν
11
1
1
1
2
3
4
4
6
1
0
0
1
3
ν
0
ν
1
ν
2
ν
3
ν
4
ν
5
ν
6
ν
7
*
ν
8
ν
9
ν
10
ν
11
1
1
1
2
3
2
2
4
1
0
0
1
3
ν
0
ν
1
ν
2
ν
3
ν
4
ν
5
ν
6
ν
7
ν
8
ν
9
ν
10
ν
11
1
1
1
2
3
2
2
3
а) б)
в)
г)
Рис. 44
Рис. 45
ν
6
ν
3
ν
1
ν
0
ν
10
ν
7
ν
4
ν
2
ν
13
ν
11
ν
8
ν
5
ν
k
ν
14
ν
12
ν
9
1
5
7
2
1
3
5
2
2
2
4
1
0
4
1
3
3
2
4
5
4
2
8
2
Страницы
- « первая
- ‹ предыдущая
- …
- 79
- 80
- 81
- 82
- 83
- …
- следующая ›
- последняя »
