Найти кратчайший путь между двумя узлами (вершинами)

Question

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

Я думаю об использовании наименьших общих предков , но края не имеют четко определенного корня, поэтому я не думаю, что решение работает.

Кратчайший путь определяется минимальным количеством пройденных вершин.

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

Answer 1

Алгоритм Дейкстры сделает это за вас.

Answer 2

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

Если у вас нет предварительных знаний о графике (если вы это делаете, вы можете использовать эвристический поиск, например A *), тогда вам следует использовать в ширину поиск .

Answer 3

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

Answer 4

Shortest path is defined by the minimum number of vertexes treversed

соответствует минимальному числу ребер плюс один.

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

Answer 5

Дополнительные 2 цента. Взгляните на networkx . Уже реализованы интересные алгоритмы для того, что вам нужно, и вы можете выбрать наиболее подходящий.