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

Question

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

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

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

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

Я знаю, что мог бы использовать алгоритм Дейкстры здесь, но меня особенно интересует анализ этого алгоритма, основанного на BFS.

Answer 1

Анализ, который вы здесь включили, близок, но не верен. Если вы предполагаете, что стоимость каждого ребра не превышает k, то ваш новый граф будет иметь O (kn) узлов (есть дополнительные узлы, добавленные на ребро) и O (km) ребер, поэтому время выполнения будет O (kn + km) , Тем не менее, вы не можете предполагать, что k является константой здесь. В конце концов, если я увеличу вес по краям, я действительно увеличу количество времени, необходимое вашему коду для запуска. Таким образом, в целом вы можете задать время выполнения O (kn + km).

Обратите внимание, что k здесь - это отдельный параметр времени выполнения, точно так же, как m и n. И это имеет смысл - большие веса дают вам большее время выполнения.

(Как примечание, это не считается алгоритмом за полиномиальное время. Скорее, это алгоритм псевдополиномиального времени , потому что число битов, необходимых для записи, вес k равен O (log k).)