Направленный граф с неотрицательными весами (матрица смежности)

График

Матрица смежности

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

Во-первых, я хочу найти все пути, которые занимают 3 «остановки» или меньше от C до C (просто пример ... могут быть любые две вершины). После исследования я обнаружил, что BFS может быть тем, что я ищу для решения этой проблемы. Прав ли я в этом предположении?

Есть два пути с 3 остановками или меньше:

C -> D -> C

C -> E -> B -> C

Я также хочу найти кратчайший путь от A до C (просто пример .. могут быть любые две вершины). Проведя небольшое исследование, я пришел к выводу, что мне следует использовать алгоритм Дейкстры. Прав ли я в этом предположении? Если так, то я видел, что есть разные реализации. Имеет ли значение, использую ли я двоичную кучу, кучу Фибоначчи или очередь?

Спасибо и дайте мне знать, если вам понадобится дополнительная информация!


java graph dijkstra breadth-first-search directed-graph
person ShadyBears    schedule 21.09.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Во-первых, я хочу найти все пути, которые занимают 3 «остановки» или меньше от C до C (просто пример ... могут быть любые две вершины). После исследования я обнаружил, что BFS может быть тем, что я ищу для решения этой проблемы. Прав ли я в этом предположении?

Да, вы. Свойство BFS заключается в том, что узлы обрабатываются в порядке уровней, поэтому вы сначала обрабатываете все узлы, которые являются соседями исходного узла, затем узлы, которые являются соседями соседей исходного узла и т. Д.

Я также хочу найти кратчайший путь от A до C (просто пример .. могут быть любые две вершины). Проведя небольшое исследование, я пришел к выводу, что мне следует использовать алгоритм Дейкстры. Прав ли я в этом предположении? Если так, то я видел, что есть разные реализации. Имеет ли значение, использую ли я двоичную кучу, кучу Фибоначчи или очередь?

Опять же, да, алгоритм Дейкстры - классическое решение таких проблем. Существуют и другие алгоритмы, лучше подходящие для некоторых особых ситуаций (например, Беллмана-Форда, если у вас есть отрицательные веса на вашем графике), но в большинстве случаев (в том числе и ваш) используйте Дейкстру. Что касается реализации, теоретически лучшая реализация основана на очереди с минимальным приоритетом, реализованной кучей Фибоначчи. Время работы этой реализации O(|E|+|V|/log|V|) (где |V| - количество вершин, а |E| - количество ребер). Однако на практике двоичные кучи часто превосходят кучи Фибоначчи, см. эту интересную тему для получения дополнительной информации.

person Miljen Mikic    schedule 21.09.2015
comment
Это правильный способ найти все пути от C к C - запускать DFS от C и путь вывода каждый раз, когда мы находим задний край до C? - person mangusta; 21.09.2015
comment
@mangusta Не уверен в этом. DFS, как и BFS, является алгоритмом обхода графа, а не поиска всех путей. Однако, если вы введете ограничение на длину пути, вы сможете избежать пометки узлов как посещенных и, таким образом, найти все пути определенной длины. Без этого ограничения и без пометки узлов как посещенных вы застрянете в бесконечных циклах. - person Miljen Mikic; 21.09.2015
comment
@mangusta Я подумал об этом немного больше. Это возможно с DFS, но чтобы получить все пути, вам нужно будет удалить узел из списка посещений после рекурсивного вызова. - person Miljen Mikic; 21.09.2015