Кратчайший путь из двух ребер между вершинами х и у проходит еще в точности через ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Макконелл Д.N. Основы современных алгоритмов Изд2


Кратчайший путь из двух ребер между вершинами х и у проходит еще в точности через одну вершину. Например, всякий путь длины два между вершинами А и Е проходит либо через вершину В, либо через вершину D. Сравнив сумму весов ребер АВ и BE с суммой весов ребер AD и DE, мы видим, что путь через вершину D короче пути через вершину В. В общем случае, если посмотреть на сумму весов ребер А и Е, где пробегает все вершины от А до I ( за исключением самих вершин А и Е), то минимальное значение суммы весов будет давать длину кратчайшего пути из двух или менее ребер.

(cкачать страницу)

Смотреть книгу на libgen

Кратчайший путь из двух ребер между вершинами х и у проходит еще в точности через одну вершину.  Например,  всякий путь длины два между вершинами А и Е проходит либо через вершину В,  либо через вершину D.  Сравнив сумму весов ребер АВ и BE с суммой весов ребер AD и DE,  мы видим,  что путь через вершину D короче пути через вершину В.  В общем случае,  если посмотреть на сумму весов ребер А и Е,  где пробегает все вершины от А до I ( за исключением самих вершин А и Е),  то минимальное значение суммы весов будет давать длину кратчайшего пути из двух или менее ребер.