Взвешенный ориентированный граф лучший метод для кратчайшего пути

Question

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

Вопрос был: есть весовой орграф G = (V, E) с n узлами и m ребрами. Каждый узел имеет вес 1 или 2. Вопрос заключался в том, чтобы выяснить, какой алгоритм использовать для нахождения кратчайшего пути в G от заданной вершины u до заданной вершины v. Возможны следующие варианты:

a) O(n+m) time using a modified BFS
b) O(n+m) time using a modified DFS
c) O(mlogn) time using Dijkstra's Algorithm
d) O(n^3) time using modified Floyd-Warshall algorithm

Ответ: а) O (n + m) время использования модифицированной BFS,

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

Answer 1

Поскольку все пути ограничены расстоянием 1 или 2, для каждого ребра длины 2 от узлов a до b вы можете просто создать новый узел c с ребром от a до c длины 1 и ребро от c до b длины 1, и тогда это становится графом только с ребрами весом 1, которые обычно BFS обычно находят кратчайший путь от u до v. Поскольку вы добавляете только O(m) новые узлы и O(m) новые ребра, это сохраняет временную сложность BFS O(n+m).

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