Дерево - кратчайший путь
Cтраница 1
 |
Дерево передачи информации узла 1. [1] |
Дерево кратчайших путей и таблица маршрутов показаны на рис. 8.11 и табл. 8.6 соответственно. [2]
Задача о дереве кратчайших путей естественно наводит на мысль об аналогичной задаче - задаче о построении дерева с минимальной суммой длин дуг. [3]
Начинаем с корня дерева кратчайшего пути. [4]
 |
Дерево крат - Покажем, что неравенство со. [5] |
Это дерево называется деревом кратчайших путей. [6]
Начинаем с корневого узла дерева кратчайших путей. [7]
Добавляем этот узел к дереву кратчайшего пути. [8]
 |
Часть дерева кратчайшего пути. [9] |
На рис. 1Z9 показана часть дерева кратчайшего пути. В этой точке алгоритм проверил узлы А и В, удалил их из списка возможных и исследовал их связи. Жирные стрелки на рис. 1Z9 указывают значение InLink в этой точке. Например, значение поля InLinknmi узла Е соответствует связи между узлами Е и В. [10]
Теперь предположим, что требуется найти для исходной сети дерево кратчайшего пути с корнем в узле D. [11]
 |
Окно программы Span.| Дерево кратчайших путей. [12] |
На рис. 12 8 изображена сеть, в которой дерево кратчайших путей с корнем в узле А выделено жирными линиями. Оно показывает кратчайшие пути от узла А до любого другого узла сети. [13]
 |
Неправильное дерево кратчайшего для сети с циклом отрицательной стоимости.| Дерево кратчайших путей с корнем в узле 3. [14] |
На рис. 12.10 показана сеть с отрицательной стоимостью цикла и дерево кратчайшего пути, которое получится, если алгоритм модифицирует стоимость уже имеющихся в дереве узлов. [15]
Страницы: 1 2 3