algorithm - 无向循环图中的最短路径

Question

有人可以解释一下如何给出一个无向图 G = (V; E); 边长 le > 0；和 E 中的边。

我们可以生成包含边 e 的最短循环的长度。

我了解如何在有向图中执行此操作，但我不确定如何使用无向图解决问题。

Answer 1

不修改图形：设e为边(u, v)。选择两个节点中的一个——我将选择u——并从 u 开始运行一个普通的 Dijkstra/BFS，并稍作修改：在进行第一跳时，你不能将v添加到队列中。现在搜索v。