小编ode*_*ght的帖子

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

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

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

任何帮助表示赞赏。