Я пытался найти решение для поиска алгоритма кратчайшего пути с одним источником для неориентированного взвешенного графа с использованием BFS.
Я придумал решение для преобразования каждого веса ребра, скажем x, в x ребер между вершинами каждого нового ребра с весом 1, а затем запустить BFS. Я бы получил новое дерево BFS, и, поскольку это дерево, существует только 1 путь от корневого узла до каждой другой вершины.
Проблема, с которой я столкнулся, заключается в том, чтобы попытаться проанализировать следующий алгоритм. Каждое ребро нужно посетить один раз, а затем разбить на соответствующее количество ребер в соответствии с его весом. Затем нам нужно найти BFS нового графа.
Стоимость посещения каждого ребра составляет O (m), где m - количество ребер, поскольку каждое ребро посещается один раз для его разделения. Предположим, что новый граф имеет km ребер (скажем, m '). Временная сложность BFS составляет O (n + m ') = O (n + km) = O (n + m), т.е. временная сложность остается неизменной. Правильно ли данное доказательство?
Я знаю, что могу использовать здесь алгоритм Дейкстры, но меня особенно интересует анализ этого алгоритма на основе BFS.
