两组顶点之间的最短路径

Question

给你一个有向加权图，它有 m 条边和 n 个顶点。每条边的权重都是非负的。顶点要么在集合 S1 中，要么在集合 S2 中（S1 和 S2 不相交）。您需要找到 任意对 (v1, v2) 之间的最短路径（v1 在 S1 中，v2 在 S2 中）。

求解的运行时间应该是O(mlogn).

'Nonnegtive' 和 'mlogn' 让我想起了 Dijkstra，但我有不知道如何使用 Dijkstra for constant times 来解决它。

提前致谢。

Answer 1

Dijkstra，但修改：

初始化

double min = infinite;     // shortest distance between n1 (of s1) and n2 (of s2)
Node n1 = null, n2 = null; // members of s1 and s2 with shortest distance between them
Set<Node> visited = new Set<>(); // initially-empty set of visited nodes of s1

运行 Dijkstra 从 s1 的每个节点开始 until

一个。您到达 s2 的节点（将起始节点添加到 visited；如果 distance < min，则更新 min、n1 和 n2）

b。你到达了已经在 visited 中的 s1 节点（将起始节点添加到 visited）

c。您运行个要访问的节点（仅当图形未连接时才有可能；将起始节点添加到 visited）
Return 结果对。

运行ning Dijkstra 是 O(m log n) worst-case，但您不会运行ning 完全 |s1| 次 - 相反，最终结果上述步骤相当于或更快（就访问的边而言）运行ning Dijkstra 每个连接的组件只完全一次。因此，整个算法就是O(m log n)

两组顶点之间的最短路径

Shortest paths between vertices in two sets

algorithm

graph

dijkstra

shortest-path