解决方案


方法:Dijkstra 算法

思路

将原始图作为加权无向图处理,我们可以使用 Dijkstra 算法查找原始图中的所有可到达结点。 但是,这不足以解决仅部分使用细分边的示例。

当我们沿着边(沿任一方向)行进时,我们可以跟踪我们使用它的程度。最后,我们想知道我们在原始图中到达的每个结点,以及每条边的利用率之和。

算法

我们使用 Dijkstra 算法 来找出从源到所有目标的最短距离。 这是一个教科书算法, 请参阅此链接了解详细信息。

另外,对于每条(有向)边 (node,nei),我们将跟踪有多少结点(从原始边细分而来的新结点)被使用。 最后,我们将总结每条边的利用率。

有关更多详细信息,请参阅内联注释。

复杂度分析

  • 时间复杂度:,其中 edges 的长度。

  • 空间复杂度: