Как сделать более быстрый алгоритм

Question

Пусть ? = (?, ?) - ориентированный граф с весами ребер, и пусть ? - вершина из ?.Все веса ребер являются целыми числами от 1 до 20. Разработайте алгоритм поиска кратчайших путей из ?.Время выполнения вашего алгоритма должно быть асимптотически быстрее, чем время работы Дейкстры.

Я знаю, что время работы Дейкстры равно O (e + v log v), и пытаюсь найти более быстрый алгоритм.

Если все веса равны 1 или включают только 0 и 1, я могу использовать BFS O (e + v) в ориентированном графе, но как сделать более быстрый алгоритм для весов ребер целыми числами от 1 до 20.

Answer 1

1. Хорошо, скажем, у вас есть ребро, которое идет от u к v с весом w
2. Мы можем вставить w-1 дополнительные узлы между узлами u и v
3. Такпосле изменения каждого ребра (которое занимает O (20 * E)) у нас есть график, где каждое ребро равно 1
4. . И на таком графике мы можем использовать обычную BFS, у нас будет не более 20 * N новых узлов, и20 * E новые ребра, так что сложность все еще O (V + E)

т.е.

Это преобразуется вэто: