Алгоритм взвешенного графика

Question

У меня есть взвешенный ориентированный граф с кратными ребрами, начиная с конца в тех же узлах. Ex. Несколько ребер, идущих от узла A к узлу B.

Каков будет наилучший алгоритм поиска для получения всех путей к определенному узлу и связанных с этим затрат этих путей?

Answer 1

Поскольку вам нужны все пути, я бы использовал простой поиск в ширину. Однако я также советую свернуть все параллельные ребра в одно ребро со списком весов.

Как только вы получите все разные пути (то есть все пути, в которых посещались узлы, разные), для каждого пути вы можете рассчитать все возможные альтернативные параллельные маршруты.

Итак, если у вас есть следующие ребра:

A -> C  (5)
A -> C  (3)
A -> B  (7)
B -> C  (1)
B -> C  (4)

Первый шаг превращает его в:

A -> C (5,3)
A -> B (7)
B -> C (1,4)

Поиск в ширину на этом графике даст следующие пути между A и B:

A -> B (7)
A -> C -> B (5,3) + (1,4)

Таким образом, для второго пути вы получите следующие расходы:

5 + 1 
5 + 4
3 + 1
3 + 4

Само по себе это не будет быстрее, чем просто сделать BFS на исходном графе, но более простой граф легче обрабатывать.

Answer 2

разрешаете ли вы ездить на велосипеде, то есть вы указали ссылку / путь от a-> b b-x-x -> a? в этом случае вы получите неограниченное количество путей.

Answer 3

Как уже говорилось, вы можете выполнять грубое отслеживание / возврат, используя поиск в глубину и т. Д.

Не ожидайте найти какие-либо ярлыки для этого - если ваш граф достаточно плотный, может быть много путей, и даже просто найти, сколько их существует, # P-завершено (т.е. : неразборчиво).

(Если ваша проблема в другом - возможно, разрешены повторяющиеся узлы или вы хотите только найти кратчайший путь или что-то в этом роде, тогда может быть найденное решение)

Answer 4

Если вам нужно вывести стоимость каждого пути, нет ничего лучше, чем простая DFS (или BFS).Так как проблема чувствительна к выводу, и у вас могут быть только O (E + V) пути, вы не можете достичь ничего лучше с точки зрения нотации big-O.