algorithm - 只有两种可能成本的完整图。从 0 到 N - 1 的最短路径成本是多少

标签 algorithm graph dijkstra shortest-path breadth-first-search

给你一个完整的无向图,有 N 个顶点。除了 K 条边之外,所有边的成本都是 A。那些 K 条边的成本是 B 并且您知道它们(作为对列表)。从节点 0 到节点 N - 1 的最小成本是多少。

2 <= N <= 500k
0 <= K <= 500k
1 <= A, B <= 500k 

显然,当这 K 条边的成本高于其他边且节点 0 和节点 N - 1 由 K 边连接时,问题就来了。

Dijkstra 不工作。我什至尝试过与 BFS 非常相似的东西。

Step1: Let G(0) be the set of "good" adjacent nodes with node 0.
Step2: For each node in G(0):
              compute G(node)
              if G(node) contains N - 1
                  return step

              else
                  add node to some queue
       repeat step2 and increment step

问题是这会占用大量时间,因为对于每个节点,您都必须从 0 到 N - 1 进行循环才能找到“好的”相邻节点。

有没有人有更好的想法?谢谢。

编辑:这是来自 ACM 竞赛的链接:http://acm.ro/prob/probleme/B.pdf

最佳答案

这是一项艰巨的案例工作:

  1. A < B 并且 0 和 N-1 由 A 加入 -> 平凡。
  2. B < A and 0 and N-1 joined by B -> trivial.
  3. B < A 并且 0 和 N-1 由 A 加入 -> 对只有 K 条边的图进行 BFS。
  4. A < B 并且 0 和 N-1 由 B 加入 -> 您可以检查 O(N) 时间是否存在长度为 2*A 的路径(尝试中间的每个顶点)。

    要检查其他路径长度,请遵循以下算法: 设 X(d) 是一组可通过使用从 0 开始的 d 条较短边可到达的节点。您可以使用以下算法找到 X(d):取具有未知距离的每个顶点 v 并迭代检查 v 与来自 X(d-1) 的顶点之间的边).如果你找到了短边,那么 v 在 X(d) 中,否则你踩到了长边。由于最多有 K 条长边,因此您最多可以踩踏它们 K 次。所以你应该在最多 O(N + K) 时间内找到每个顶点的距离。

关于algorithm - 只有两种可能成本的完整图。从 0 到 N - 1 的最短路径成本是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23030181/

相关文章:

algorithm - 如何知道 Big O 何时是对数的?

java - 加到 n 的 1 + 2 的所有组合

python - 如何在 Networkx 和 matplotlib 中标记多图的边缘?

javascript - D3 TreeMap - 文本中心、控制高度和链接箭头奇怪行为

Networkx - 获取 Dijkstra 路径中的边缘属性

algorithm - Dijkstra 算法的负循环

algorithm - 汇编语言使用有符号整型乘法数学来执行移位

algorithm - 给定一个随机顺序的整数数组,你必须找到最小交换次数才能将其转换为循环排序数组

以最高效率访问无向图中所有节点的算法?

c++ - Dijkstra 的 - 队列