graph - 如何计算源和目标相同的图中两个节点之间的最短路径？

Question

如何计算源和目标相同的图中两个节点之间的最短路径？

图形：

A->B(5)
A->D(5)
A->E(7)
B->C(4)
C->D(8)
C->E(2)
D->C(8)
D->E(6)
E->B(3)

例如，B 和 B 之间的最短路径是什么？我尝试使用 dijkstra 但没有用，它总是在第一步返回 B->B 。

正确答案：B->C->E->B

Answer 1

将顶点一分为二：B1 和 B2，其中原图中所有从 B 开始的边都将从 B1 开始；所有在 B 中终止的边都将在 B2 中终止。

之后，您可以运行 Dijkstra 在修改后的图中找到从 B1 到 B2 的最短路径。

注意：如果要保留图中的所有路径，请添加附加边 B2->B1。这不会改变循环搜索的结果，原始图中和修改后的图中的所有路径都是等价的