如何制作更快的算法
How to make a faster algorithm
令 = (, ) 为具有边权重的有向图，令 为 的顶点。所有的边权重都是 1 到 20 之间的整数。设计一个算法来找到从 的最短路径。你算法的 运行 时间应该比 Dijkstra 的 运行 时间渐进快。
我知道Dijkstra的运行时间是O(e + v log v)，想找一个更快的算法
如果所有权重都是 1 或只包括 0 和 1，我可以在有向图中使用 BFS O(e+v)，但是如何为边缘权重制作一个更快的算法是 1 到 20 之间的整数。
- 好吧，假设你有一条从 u 到 v 的边，权重为
w
- 我们可以在节点 u 和 v 之间插入 w-1 个额外节点
- 所以之后
修改每条边（需要 O(20*E)）我们有一个图，其中
每条边都是 1
- 在这样的图上我们可以使用常规的 BFS，我们最多有 20*N
新节点和 20*E 条新边，所以复杂度仍然是 O(V+E)
即
这将转换为：
令 = (, ) 为具有边权重的有向图，令 为 的顶点。所有的边权重都是 1 到 20 之间的整数。设计一个算法来找到从 的最短路径。你算法的 运行 时间应该比 Dijkstra 的 运行 时间渐进快。
我知道Dijkstra的运行时间是O(e + v log v)，想找一个更快的算法
如果所有权重都是 1 或只包括 0 和 1，我可以在有向图中使用 BFS O(e+v)，但是如何为边缘权重制作一个更快的算法是 1 到 20 之间的整数。
- 好吧，假设你有一条从 u 到 v 的边，权重为 w
- 我们可以在节点 u 和 v 之间插入 w-1 个额外节点
- 所以之后 修改每条边（需要 O(20*E)）我们有一个图，其中 每条边都是 1
- 在这样的图上我们可以使用常规的 BFS，我们最多有 20*N 新节点和 20*E 条新边，所以复杂度仍然是 O(V+E)
即
这将转换为：