在 O(V + E) 时间内在加权无向图中找到从源到目标的最短路径

Question

我的任务是设计一种算法，该算法在 O(V + E) 时间内在具有 V 个节点和 E 条边的加权无向图中找到最短路径。图的权重都是正整数，没有权重大于 15。

我相信我可以使用 Dijkstra 算法来找到从源节点到目标节点的最短路径，但我认为它不满足运行时约束。

了解 BFS 和 DFS 的运行时，我认为对这些算法进行某种修改将使我达到 O(V + E)，但我不确定要朝哪个方向前进或如何利用 < = 15 边缘权重约束。

任何帮助表示赞赏。

Answer 1

您可以使用 Dijkstra 算法，但您必须对优先级队列稍加小心。

由于所有的权重都是从 1 到 15 的整数，因此在任一时刻队列中只能有 16 个不同的优先级。您可以利用这一事实在恒定时间内实现所有优先级队列操作。这会将算法的复杂度从 O(|V| + |E| log |V|) 更改为 O(|V| + |E|)

有很多方法可以制作该优先级队列。基本上，您将条目划分为具有相同优先级的条目列表，然后您只需对 16 个列表进行优先级排序。将这 16 个列表保存在一个循环数组中是合理的。