如何找到不在任何最短路径上的所有边？

Question

因此，这个问题出现在上个月的APAC上。https://code.google.com/codejam/contest/4284486/dashboard#s=p2

问题如下：

问题

G公司的主园区有N个办公室(编号从0到N- 1)和M条双向道路(编号从0到M- 1)。第i条道路连接两个办公室(Ui，Vi)，在它上面行驶(两个方向)需要Ci分钟。

两个办公室X和Y之间的路径是一系列从X开始到Y结束的一条或多条道路。行进路径所用的时间是组成路径的每条道路行进所需时间的总和。(保证至少有一条路径连接任何两个办公室。)

G公司专门研究高效的交通解决方案，但首席执行官刚刚意识到，令人尴尬的是，它自己的道路网络可能不是最优的！她想知道校园里哪些道路是低效的。如果且仅当没有包含在任何办公室之间的任何最短路径中时，一条道路才是低效的。

根据办公室和道路的图表，你能帮助CEO找到所有效率低下的道路吗？

输入

输入的第一行给出了测试用例的数量，T. t测试用例紧随其后。每个案例都以一行开头，其中包含两个整数N和M，表示办公室和道路的数量。随后是M行，每行包含三个整数: Ui、Vi和Ci，表示第i条路在office Ui和office Vi之间，在上面行驶需要Ci分钟。

输出

对于每个测试用例，输出一行包含“case #x:"，其中x是测试用例编号(从1开始)。然后以递增的顺序输出所有低效道路的道路编号，每条道路都在自己的行上。(请注意，道路0指的是测试用例中列出的第一条道路，道路1指的是第二条道路，依此类推)

现在，我正在尝试将Djisktra的算法应用于这个问题，但我真的不能思考如何才能做到这一点？

所以，djikstra基本上是这样的，每次都在数组中找到最小距离，但是我如何才能准确地应用它呢？伪代码就是我所需要的。谢谢!

Answer 1

使用Dijkstra的最短路径算法对每对节点进行最短路径搜索，假设

实现，则会添加一个

因素，因为您必须为图中的每对节点执行此操作(此外，它可能不是一个使用可变堆的非常容易编码的算法)。

一个简单的解决方案是all pairs shortest path with Floyd-Warshall，然后检查每个距离，如果这是找到的最短距离。

想法是这样的:假设你有这个图

​

​

通过动态编程实现(查看我发布的完整代码的链接)，通过递归地将每个节点K视为连接两个节点X和Y的路径中的中间节点，即

for each node K
  for each pair of nodes X and Y
    if the distance X -> K + K -> Y is less than the distance X -> Y
      X -> K -> Y is a better path than X -> Y, update the distance X -> Y

请注意，这是一个缓慢的

然而，所有对最短路径的解决方案和更好的算法都是可用的。

来源：all pairs shortest path with Floyd-Warshall