c# - 选定顶点中的路由算法

Question

我想选择我必须通过的起点、终点和顶点，算法应该找到最短的路由路径。我有一个存储 Routes Id|Name|StoreA|StoreB|Kilometers 的表，其中 StoreA 和 StoreB 是 Store 表中的 FK。我仅以一种方式保存数据。示例：在表 Routes 1|Lidl-Kaufland|1|2|157 中，而不是返回，因为距离相同。我不确定我是使用 QuickGraph 库中的 BidirectionalGraph 还是 UndirectedGraph。

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

Answer 1

听起来绝对像是一个旅行推销员的问题。有两种方法可以解决这个问题。

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

希望这可以帮助。