如何解决这样一个多起点、多终点的最短路径问题？
如何解决这样一个多起点、多终点的最短路径问题？
提问于 2021-10-23 06:27:14
在图形上，有多个起点和终点。每个起点对应于多个终点，而每个终点仅对应于一个起点。我需要在地图上找到从起点到终点的所有路线。不同的路线不能交叉，但允许它们重叠。
在开始时，我使用A*算法来寻找每一条路由，但后一条路由采用了更多的路径，以避免与前一条路由交叉。我想知道是否有一个算法可以考虑所有路由的总长度。
回答 1
Stack Overflow用户
发布于 2021-10-23 12:51:59
请澄清你所说的“交叉通道”是什么意思。
我似乎可以看到两种可能性。
交叉路径出现在具有四条或更多条边的顶点上。一条路径使用两条边进入和离开顶点，第二条路径使用不同的一对边。
或
B.顶点的x，y位置都在同一平面上。当两条边相交时，节点之间会发生交叉。
算法：
- 循环开始节点
- 使用Dijkstra查找从开始节点到所有相应结束节点的最短路径
- 如果没有交叉发生，则完成此开始节点
- 从图中删除交叉节点(A)或链路(B)，并依次重新计算交叉路径。选择最便宜的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69685701
复制相关文章
相似问题
腾讯云开发者
