Учитывая подключен , неориентированный граф G , A кратчайшего пути дерево с корнем в вершине V является остов Т из G , таким образом, что расстояние пути от корня V к любой другой вершины U в Т представляет собой кратчайший путь расстояние от V до U в G .
В связных графах, где кратчайшие пути четко определены (т. Е. Отсутствуют циклы отрицательной длины), мы можем построить дерево кратчайших путей, используя следующий алгоритм:
- Вычислите dist ( u ), кратчайшее расстояние от корня v до вершины u в G, используя алгоритм Дейкстры или алгоритм Беллмана – Форда .
- Для всех некорневых вершин u мы можем назначить u родительскую вершину p u такую, что p u соединена с u , и что dist ( p u ) + edge_dist ( p u , u ) = dist ( u ). В случае, если существует несколько вариантов p u , выберите p u, для которого существует кратчайший путь от v до p u с как можно меньшим количеством ребер; это правило разрыва связей необходимо для предотвращения зацикливания, когда существуют циклы нулевой длины.
- Постройте дерево кратчайшего пути, используя ребра между каждым узлом и его родителем.
Вышеупомянутый алгоритм гарантирует существование деревьев кратчайших путей. Как и минимальные остовные деревья , деревья кратчайших путей в целом не уникальны.
В графах, у которых веса всех ребер равны единице, деревья кратчайших путей совпадают с деревьями поиска в ширину .
В графах с отрицательными циклами набор кратчайших простых путей от v до всех остальных вершин не обязательно образует дерево.
См. Также [ править ]
Ссылки [ править ]
Кан, Роберт С. (1998). Дизайн глобальной сети: концепции и инструменты для оптимизации . Сеть. Морган Кауфманн. ISBN 978-1558604582.
.svg){kind=small} | Эта статья о комбинаторике незавершена . Вы можете помочь Википедии, расширив ее . |
