algorithm - 在 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 个列表保存在一个循环数组中是合理的。