小编Tal*_*lor的帖子

让 = (, ) 是一个有边权重的有向图，让 是 的顶点。所有的边权重都是 1 到 20 之间的整数。设计一个算法来从 中找到最短路径。算法的运行时间应该比 Dijkstra 的运行时间渐进快。

我知道 Dijkstra 的运行时间是 O( e + v log v)，并尝试找到更快的算法。

如果所有的权重都是 1 或者只包含 0 和 1，我可以在有向图中使用 BFS O(e+v)，但是如何为边权重制定更快的算法是 1 到 20 之间的整数。