Какой алгоритм мне следует использовать, чтобы получить все возможные пути в ориентированном взвешенном графе с положительными весами?

Question

У меня есть ориентированный взвешенный граф с положительными весами, который выглядит примерно так: - введите описание изображения здесь

Я пытаюсь сделать следующее: -

1. Найти все возможные пути между двумя узлами.
2. Упорядочить пути в порядке возрастания на основе длина их пути (определяемая весами ребер), скажем, по крайней мере, 5 первых.
3. Используйте для этого оптимальный способ, чтобы даже в случае большего количества узлов программа не занимала много времени вычисления.

Например: - Скажем, мой начальный узел - d, а конечный узел - c. Таким образом, результат должен быть примерно таким:

d to c = 11
d to e to c = 17
d to b to c = 25
d to b to a to c = 31
d to b to a to f to c = 38

Как я могу этого добиться?

Answer 1

Лучшим подходом было бы использовать алгоритм Dijkstra’s shortest path, мы можем получить кратчайший путь за O(E + VLogV) время.

Воспользуйтесь этим базовым c подходом, который поможет вам найти кратчайший путь:

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

Запишите эти расстояния на узле - перезапись бесконечности - а также вычеркните узлы, означая, что их кратчайший путь был найден.

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

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

Повторяйте шаг 2, пока все узлы не будут вычеркнуты. Теперь у нас есть график, в котором значения, хранящиеся в любом узле, будут кратчайшим расстоянием до него от начального узла.

Answer 2

Найдите все возможные пути между двумя узлами

Здесь вы можете использовать брутфорс, но возможно, что у вас будет много путей, и для больших графиков действительно потребуются годы (> 100 узлов, в зависимости от множества факторов).

Расположите пути в порядке возрастания на основе их длины пути (как указано весами ребер), скажем, по крайней мере, 5 верхних.

Просто отсортируйте их и возьмите 5 первых. (Вы можете использовать комбинацию списка ребер и целого числа / двойного числа для длины пути).

Используйте оптимальный способ сделать это, чтобы даже в случаях большего количества узлов, программа не займет много времени вычислений.

Даже нахождение всех возможных путей между двумя узлами NP-Hard ( Source , это для неориентированных графов, но все же действительный). Вам нужно будет использовать эвристику .

Что вы имеете в виду под большим количеством узлов? Вы имеете в виду 100 или 100 миллионов? Это зависит от вашего контекста.