我必须解决这个问题，这已经困扰了我好几个小时，而且我似乎找不到能够满足所需时间复杂性的有效解决方案。
对于任何图形G中的任意边e，让G \ e表示通过从G中删除e而获得的图形。
（a）假设我们得到了一个边缘加权有向图G，其中从顶点s到顶点t的最短路径σ穿过< [G。描述一种算法，计算G中每个边[[e，在O]中从s到t] （VlogV）时间。您的算法应输出一组E最短路径距离，对于输入图的每个边缘一个。您可能会假设所有边缘权重都是非负的。[提示：如果我们删除原始最短路径的边，那么旧的和新的最短路径将如何重叠？[（b）描述一种算法，用于解决O（V log V）时间内任意无向图的替换路径问题。
我必须解决这个问题，这已经困扰了我好几个小时，而且我似乎找不到能够满足所需时间复杂性的有效解决方案。对于任何图形G中的任意边e，让G \ e表示...首先，我要指出的是，复杂度不仅取决于V，因为输出应包含E值，因此我想它应该是O（E + Vlog（V））。