В табл. а) дан частичный порядок по протяженности ребер графа, а табл. b) результаты пошагового построения остова. табл. а)
|
l58 |
l79 |
l57 |
l01 |
l67 |
l89 |
l23 |
l24 |
l35 |
l46 |
l45 |
l02 |
l13 |
|
5 |
5 |
8 |
10 |
10 |
10 |
12 |
12 |
15 |
15 |
20 |
24 |
32 |
табл. b)
|
ш а г |
ребра, включаемые в остов |
вершины, включаемые в остов |
|||||||||||||||||
|
l58 |
l79 |
l57 |
l67 |
l01 |
l24 |
l23 |
l35 |
l02 |
x5 |
x8 |
x7 |
x9 |
x6 |
x0 |
x1 |
x2 |
x4 |
x6 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
3 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
4 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
5 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
6 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
8 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
9 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
lij |
5 |
5 |
8 |
10 |
10 |
12 |
12 |
15 |
24 |
L=5+5+8+10+10+12+12+15+24=101. |
|||||||||
3.4.3 Поиск кратчайших путей в сети.
Подобные задачи возникают при выборе маршрутов в вычислительных сетях и транспортных системах. В вычислительных сетях решение подобных задач определяет состав и структуру сетевых протоколов для обслуживания движения пакетов информации. По данным о загрузке каналов вычисляется наиболее оптимальный маршрут прохождения пакета информации. При нахождении такого пути к пакету добавляется заголовок, в котором содержится указывают перечень узлов для перехода от вершины хi к вершине хj или очередную вершину перехода. В транспортных системах решение подобных задач определяет наиболее экономный по стоимости или по времени маршрут движения транспортной единицы.
Каждая вершина в таком графе используется только один раз, а длина кратчайшего пути определится суммой весов ребер для перехода ni,j=(хi;...хk;...хj):
Li,j=m,nå lm,n, где i£m, n£j, m¹n.
Для поиска кратчайших путей есть несколько алгоритмов. Алгоритмы Форда-Беллмана и Дейкстра позволяют найти кратчайшие пути от заданной вершины графа до любой другой. В результате этих вычислений формируется
граф типа “дерево” с корнем в заданной вершине. Алгоритмы Флойда и Данцига позволяют искать кратчайшие пути между любой парой вершин графа типа сеть.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.