Используйте BFS, чтобы найти кратчайший путь между 2 узлами
Я новичок в теории графов и мне нужна небольшая помощь. Допустим, у нас есть граф с заданным начальным и конечным верстекстом. Как получить кратчайший путь ТОЛЬКО между начальной и конечной вершинами, используя BFS.
Я написал программу, которая вычисляет кратчайший путь во всем графе, но не знаю, как его реализовать, когда я хочу «ограничить дерево» только этими вершинами между началом и концом.
Любая помощь, псевдокод, советы будут с благодарностью.
Решение
Алгоритм BFS получает вершину в графе и вычисляет кратчайший путь от этой вершины ко всем остальным вершинам. Когда достигает какой-то вершины, BFS уже нашли кратчайший путь к ней. Поэтому вам не нужно продолжать алгоритм, если вам нужен только кратчайший путь к этой вершине. Вы должны закончить алгоритм, когда он достигнет желаемой вершины.
Другие решения
Других решений пока нет …