Дерево кратчайшего пути
В математике и информатике дерево кратчайшего пути с корнем в вершине v связного v неориентированного является графа G остовным деревом T графа G , такое что расстояние пути от корня до любой другой вершины u в T является кратчайшим путем. расстояние 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 ко всем остальным вершинам не обязательно образует дерево.
Для простых связных графов можно использовать деревья кратчайших путей. [1] предложить нелинейную связь между двумя мерами центральности сети : близостью и степенью . Предполагая, что ветви деревьев кратчайших путей статистически подобны для любого корневого узла в одной сети, можно показать, что размеры ветвей зависят только от количества ветвей, соединенных с корневой вершиной, т. е. от степени корневой узел. Из этого следует, что обратная величина близости, масштаб длины, связанный с каждой вершиной, изменяется примерно линейно с логарифмом степени. Связь не точная, но она отражает корреляцию между близостью и степенью в большом количестве сетей, построенных на основе реальных данных. [1] и этот успех предполагает, что деревья кратчайших путей могут быть полезным приближением в сетевом анализе.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б Эванс, Тим С.; Чен, Биншэн (2022). «Связывание центральности сети измеряет близость и степень» . Физика связи . 5 (1): 172. дои : 10.1038/s42005-022-00949-5 . hdl : 10044/1/97904 . ISSN 2399-3650 .
Ссылки
[ редактировать ]Кан, Роберт С. (1998). Проектирование глобальной сети: концепции и инструменты оптимизации . Сеть. Морган Кауфманн. ISBN 978-1558604582 .
 | Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |