在所选顶点中路由的算法

Question

我想选择我必须通过的起点、终点和顶点，算法应该找到最短的路由路径。我有 table 存储路线 ID|名称|StoreA|StoreB|公里，其中 StoreA 和 StoreB 是来自商店 table.I 的 FK，仅以一种方式保存数据。 Example:in table 路线 1|Lidl-Kaufland|1|2|157 而不是回程，因为距离是 same.I 我不确定我是使用 QuickGraph 库中的 BidirectionalGraph 还是 UndirectedGraph .

例如这个路网：1: http://i.stack.imgur.com/mxcWe.png 首先我选择这 4 个顶点然后我选择开始和结束一个。 我使用 QuickGraph 3.6，这里最大的问题是我应该使用什么图，是否有适合我目的的算法？谢谢大家，我希望我解释了所有必要的内容来回答我。

Answer 1

听起来绝对像是旅行推销员问题。有两个是接近这个。

1. 如果您想将图修剪成一棵树，使图的总成本最低，请尝试使用 Prim 或 Kruskal 的最小生成树算法。这最终将为您提供现有图表中的最低总成本图表。
2. 如果你想在最短的时间内走完图中的所有节点并回到起始节点，你可以试试旅行商算法。
3. 如果这是一个实际的道路网络，那么您可能想要使用有向图，有些道路是单向的，有些是双向的。所以你不可能说你总是有相同的距离回来。
4. 如果您想要开箱即用的解决方案，请尝试 PostGis, PostGreSql and PgRouting。由于您已经将数据保存在数据库中，因此您可以自己开箱即用地使用所需的算法。

希望这对您有所帮助。