algorithm - 图算法中的距离beetwen顶点

Question

我自己的问题：

设 G 是一个有 n 个顶点和 m 个边的无向图。
我们有一个从 v_1 到 v_2 的列表，但现在它并不重要。
每条边的权重等于 X。
我们的任务是找到从 v_i 到 v_j 的最快路径为 w = 2X 的所有对 (v_i, v_j)。

（看例子）

有可能比 brute v * dikstra 或 v*v?? 这个问题能在 O(n^2) 时间内解决吗？哪种算法最好？感谢您的每一个帮助。

例子：

    n = m = 5
    v_1 -> v_2 -> v_3 -> v_4 -> v_5 and v_1 -> v_3

解决方案：

(1,4), (2,4), (3,5)

从 v_1 到 v_4 的最短路径是 2X（与其他解决方案相同）。

编辑：我们有邻接列表。

score 1 · Accepted Answer

有可能比 brute v * dikstra 或 v*v?? 这个问题可以在 $O(n)$ 或 $O(n log n)$ 时间内解决吗？

你不能变得更好O(n^2)（ = O(v*v)），因为输出可能包含O(n^2)不同的条目，例如：

          a
          |
     b----c----d
          |
          e

从每个顶点到每个顶点都有一条长度为 2 的路径，除非源/目标 = c。概括此图将使您O(n^2)与所需的距离配对

1 回答 1