Я видел алгоритм Дейкстры для взвешенных графов. Что мне делать, чтобы реализовать это, чтобы найти кратчайший путь в невзвешенном графе?
Должен ли я считать веса между всеми ребрами 0 или 1?
Во-вторых, я хочу реализовать bfs на 10^5 узлах, чтобы проверить, доступен ли узел с любого другого узла? Возможно ли, поскольку определение двумерного массива [10^5][10^5] дает ошибку памяти.
Что касается вашего первого вопроса, я реализовал Dijkstra на невзвешенном пути с весом 1, он работает нормально, но может быть лучшее решение.
Я мало что помню про bfs, извините!
Вы можете представить себе невзвешенный граф как каждое ребро, имеющее вес 1.
Для BFS на большом графике взгляните на алгоритмы больших данных, которые используют "внешнюю" память (жесткий диск) для хранения полного графика и используют эффективные уловки доступа к этим данным, так что части, над которыми работает алгоритм, вписываются в память. для начала см .: http://www.win.tue.nl/~hermanh/teaching/2IL35/AMM/04-elementary-graph-algorithms.pdf
Использование 0 в качестве стоимости дуг приведет к одинаковой стоимости для всех возможных путей в графе, и поэтому любой может быть кратчайшим.
Использование 1 означает, что все ваши дуги имеют одинаковую стоимость, поэтому Дейкстра найдет путь, который минимизирует количество дуг между вашим началом и вашей целью. Конечно, этому условию может соответствовать несколько путей, поэтому алгоритм вернет один из них.
Надеюсь, мой ответ поможет.
