java - 如何找到完成旅程的最短路线？

Question

假设我们有一个无向图：

{A,B} 5

{A,C} 6

{A,D} 3

{A,E} 4

{B,C} 4

{B,D} 3

{B,E} 6

{C,D} 3

{C,E} 5

{D,E} 5

其中数字代表重量。

假设我有兴趣从 A 出发并参观 B、C 和 E。我怎样才能找到最短的路线来进行这次旅行？没有目的地，我只想通过旅行最短距离的那三个顶点。我在堆的帮助下使用 Dijkstra 算法，我如何修改算法来实现这一点，因为没有最终目的地。

Answer 1

一种简单的方法，可能不是最有效的，但易于实施。

1. 生成您要访问的节点的所有排列，在您的示例中：

• A -> B -> C -> E
• A -> B -> E -> C
• A -> C -> B -> E
• A -> C -> E -> B
• A -> E -> B -> C
• A -> E -> C -> B

2. 对于每个可能的序列，使用 Dijkstra 计算路径

• 例如对于 ABCE，PATH = dist(A,B) + dist(B,C) + dist(C,E)

3. 选择最短的计算路径

其他可能的方法，在这里，最后有一个相对复杂度的比较表：

https://www.baeldung.com/cs/shortest-path-to-nodes-graph