graph-theory - 如何解决这样一个多起点多终点的最短路径问题？

Question

在图上，有多个起点和终点。每个起点对应多个终点，每个终点只对应一个起点。我需要在地图上找到从起点到终点的所有路线。不同的路线不能交叉，但允许它们重叠。

一开始我使用 A* 算法来寻找每一条路线，但后一条路线为了不与前一条路线交叉而采取了更多的路径。我想知道是否有一种算法可以考虑所有路线的总长度。

标签： graph-theoryshortest-path

Answer 1

请澄清您所说的“交叉路径”是什么意思

我可以看到似乎有两种可能性。

A. 交叉路径出现在具有四个或更多边的顶点处。一条路径使用两条边进入和离开顶点，第二条路径使用不同的一对边。

或者

B. 顶点的 x,y 位置都在同一平面上。当两条边相交时，节点之间会发生交叉。

---

算法：

• 循环开始节点
• 使用 Dijkstra 找到从起始节点到其所有相应结束节点的最短路径
• 如果没有发生交叉，则为此起始节点完成
• 从图中删除交叉节点（ A ）或链接（ B ）并依次重新计算交叉路径。选择最便宜的。