graph-theory - 计算通过圆弧 (u, v) 的最短路径的数量

Question

给定一个有n 个顶点和m个弧 ( n < 1500, m < 5000 ) 和一个弧(u, v)的有向加权图。并回答问题是有多少最短路径（可以从任何位置a开始并在b结束，使得a! = b）通过给定的弧。

示例：
n = 4, m = 4
arc (1, 2) with weight is 5
arc (2, 3) with weight is 5
arc (3, 4) with weight is 5
arc (1, 4) with weight is 8
and弧 (1, 2)。
答案是 2，因为弧 (1, 2) 在最短路径 1->3 和 1->2 中。

Dijkstra可以解决这个问题吗？

标签： graph-theoryshortest-path

Answer 1

一个快速的想法是，由于这完全是关于路径重建，因此与为每个节点Floyd-Warshall's algorithm运行相比，您可以以更便宜的方式找到每对节点之间的最短路径Dijkstra's algorithm。之后，通过对每个节点进行路径重建，您只需检查提供的弧是否存在于找到的路径上。
（但请注意，Floyd-Warshall 的算法不支持负循环图）