选择顶点的路由算法

Question

我要选择我必须经过的起点、终点和顶点，算法要找到最短路径进行路由。我有一个存储路由Id|Name|StoreA|StoreB| km的表，其中StoreA和StoreB是来自Store表的fk。我只以一种方式保存数据。示例:在表Routes 1|Lidl-Kaufland|1|2|157中不包含way back，因为距离是一样的。我不确定是否从QuickGraph库中使用BidirectionalGraph或UndirectedGraph。

例如:Road Network: 1: https://i.stack.imgur.com/mxcWe.png首先，我选择这4个顶点，然后我选择开始和结束的一个。我使用QuickGraph 3.6，这里最大的问题是我应该使用什么图形，有适合我的算法吗?谢谢大家，我希望我解释的一切都有必要回答我。

Answer 1

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

1. 如果你想将图修剪成一个总成本最小的树，请尝试Prim或Kruskal的最小生成树算法。这最终会给你最小总成本图从现有的图中。
2. 如果你想在最短的时间内遍历图中的所有节点并返回到起始节点，你可以尝试旅行推销员算法。
3. 如果这是一个实际的道路网络，那么你可能想要使用有向图，有些道路是单向的，有些是双向的。所以你不可能说回来的距离总是相同的。
如果你想要一个开箱即用的解决方案，试试PostGis, PostGreSql和p注浆。当你已经在数据库中保存数据时，你可以自己帮助自己使用开箱即用的算法。

希望这对你有帮助。