Дерево - кратчайший путь
Cтраница 2
Может ли так случиться, что порядок добавления ребер к дереву кратчайшего пути совпадает с порядком их появления при обходе дерева по уровням. [16]
 |
Связный граф с тремя компонентами двусвязности. [17] |
Может ли так случиться, что порядок добавления ребер к дереву кратчайшего пути совпадает с порядком их появления при обходе дерева в глубину. [18]
Алгоритм расстановки меток всегда выбирает связь, которая гарантированно находится в дереве кратчайших путей. После удаления из списка возможных узел добавляется к дереву и уже не будет помещен в список - Алгоритм коррекции меток всегда выбирает первый узел из списка возможных, который не всегда является лучшим выбором. Значения полей Dist и InLinKnaH-ного узла могут и не быть лучшими возможными значениями. Но в конце концов алгоритм отыщет в списке узел, через который проходит более короткий путь к выбранному узлу. Тогда алгоритм обновляет поля Di st и InLink неправильно выбранного узла и помещает этот узел обратно в список возможных. [19]
Класс TLink включает поле InTree, которое указывает, является ли ребро частью дерева кратчайшего пути. [20]
Поскольку линия 5 6 не задействована при передаче информации от узла 2, то его дерево кратчайших путей и таблица маршрутов, найденные в задаче 1, останутся без изменений. [21]
Это не случайно - можно построить сетевую транспортную задачу, решение которой как раз и будет давать дерево кратчайших путей. [22]
Алгоритм удаляет выбранный узел из списка и устанавливает для него значение поля Status в значение nsWasInList, поскольку теперь выявляется постоянной частью дерева кратчайшего пути. Поля Dist и 1пЫпКузлауже имеют правильные значения. Для каждого корневого узла значение поля InLink равно nil, а значение поля Dist - нулю. [23]
Алгоритмы поиска кротчайшего пути ( shortest path), рассмотренные в следующих разделах, находят все кратчайшие пути от одной точки сети до любой другой, конечно, если сеть связана. Набор связей, используемых всеми кратчайшими путями, образует дерево кратчайших путей. [24]
Алгоритмы расстановки И коррекции меток используют список возможных связей, чтобы отслеживать узлы, которые могут быть добавлены кдереву кратчайшего пути, но по-разному управляют этим списком. Алгоритм расстановки меток всегда выбирает связь, которая обязательно окажется частью дерева кратчайшего пути. Алгоритм коррекции меток, описанный в этом разделе, выбирает любой узел в начале списка возможных связей. [25]
Если сравнить алгоритмы расстановки и коррекции меток, видно, как они похожи. Разница заключается в том, как каждый из них выбирает элементы из списка возможных узлов для вставки в дерево кратчайшего пути. [26]
Найти кратчайший путь к узлу, разбитому на несколько узлов, несколько про-пв. Чтобы отыскать кратчайший путь между узлами i и j ( узел j был разбит на подузлы), сначала найдите обычное дерево кратчайшего пути с корнем в узле i. Затем проверьте каждый из частейузла ], чтобы определить, какойиз них ближе ккор-ню. [27]
Единственное изменение требуется внести в ту часть алгоритма расстановки меток, которая выполняется сразу после того, как алгоритм нашел в списке возможных узлов узел с наименьшим значением Dist. Перед удалением узла из списка алгоритм должен проверить, является ли данный узел конечным. Если это так, то дерево кратчайшего пути уже содержит правильный путь от начального до конечного узла, и алгоритм может завершить работу. [28]
 |
Часть дерева кратчайшего пути. [29] |
Затем алгоритм перебирает список кандидатов в поисках узла с минимальным значением поля Dist. В этой точке значения поля Dist узлов С, D и Е равны 10, 21 и 22 соответственно, поэтому алгоритм выбирает узел С. Теперь узел С является частью дерева кратчайшего пути, него поля Dist и 1пЬшЬимеют правильные значения. [30]
Страницы: 1 2 3