Кратчайшая последовательность узлов через невзвешенный граф

Question

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

Я рассматриваю решение этой проблемы, предпринимая исследовательские шаги от узлов головы и хвоста и до тех пор, пока узлы с обоих концов графика не коснутся и т. Д., Но я хотел бы знать, существует ли «лучшее колесо» до ) придумать одну.

Answer 1

Используйте поиск в ширину , который выполняется в O (E + V).Это самый быстрый результат на невзвешенном графике.

Answer 2

Это одна из прекрасных «стандартных» проблем информатики. Учитывая ваше описание графика, вы должны сначала взглянуть на алгоритм Дейкстры

Answer 3

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

Вы также можете нарисовать дерево BFS, которое точно скажет вам кратчайший маршрут между источником и любым (также единственным) узлом.