Для удовольствия Я изучаю теорию графов, и я столкнулся с этой проблемой. Принимая во внимание множество вершин V, множество ребер Е, и вес для каждого ребра Е, как можно эффективно построить график G таким образом, чтобы:Как эффективно построить связный граф?
края в Е направлены, когда все ребра Е присутствуют может быть циклов.
См. Minimum Spanning Tree Алгоритмы.
Читайте алгоритм Беллмана-Форда. Он поддерживает отрицательные весовые циклы. Алгоритм Дейкстры более эффективен, но не поддерживает отрицательные весовые циклы.
Чтобы добавить к ответу ars, если ваш график содержит ребра с отрицательным весом, проблема становится более сложной (и если у вас есть цикл отрицательного веса) может возникнуть проблема.
ok ... Могу ли я узнать, что такое MrDatabase? Алгоритмы SSSP (dijkstra, Bellman-Ford) - это вариации MST, о которых только что говорилось. Dijkstra не решает проблему отрицательного веса, в то время как Bellman-Ford делает.
MSP не всегда дает то же решение, что и SSSP. Отрицательные весовые циклы не являются проблемой в MSP, поскольку мы просто минимизируем сумму весов ребер. – redtuna
«Редактирование: ребра в E направлены, когда присутствуют все ребра в E, могут быть циклы», упоминается в вопросе. MST для ациклических графов, мы не можем использовать MST, Prim, Kruskel или другие MST algos для этой проблемы. Мы можем использовать Bellman-Ford для отрицательных циклов и Dijkstra для положительных циклов. Да SSSP может начинаться с определенного узла, но рассказывать мне о некотором алгоритме MST, который может позволить циклы? –
Это алгоритмы кратчайшего пути с одним источником, а не то, что происходит после OP. –
Что он после? Могу ли вы, пожалуйста, сказать, разрешает ли какой-нибудь алгоритм MST циклы? –