时间戳

首页 > 解决方案 > 运行时间 O(kn + m) 的最短路径树算法

algorithm - 运行时间 O(kn + m) 的最短路径树算法

问题描述

有没有一种算法可以在 O(kn + m) 的运行时间内在权重为 0、1、...、k 的有向图中构建最短路径树，其中 n 是顶点数，m 是数边缘？

我认为 Dijkstras 算法可能会满足这一点，但它不依赖于边缘的权重。（我很困惑这怎么可能是这种情况）。

这样的算法会是什么样子？

标签： algorithmruntimeshortest-path

解决方案

关键是（非循环）图的拓扑排序，它允许轻松计算到每个顶点的距离。该方法具有 O(n + m) 复杂度：

1) Initialize dist[] = {INF, INF, …} and dist[s] = 0 where s is the source vertex.
2) Create a Topological order of all vertices. [complexity: O(n+m)]
3) For every vertex u in topological order: [complexity: O(n+m)]
       For every adjacent vertex v:
            If (dist[v] > dist[u] + weight(u, v)):
                dist[v] = dist[u] + weight(u, v)

步骤 3 还立即提供了通过图的最短路径。

推荐阅读