algorithm - A 和 B 之间的路线，车站之间

Question

我显然是透过树木错过了森林......

我知道旅行商问题，但是还有其他算法/问题更符合我的需求/描述吗？我需要借助这样的数学描述来描述我的问题。

我有最多五个已知起点和终点的点。所以我只需要计算访问这两个点之间所有三个点的最短路径。 Dijkstra 和类似算法试图找到两点之间的最短路径，因此在这里它们可能不会访问之间的所有点。还是有一种算法可以找到最短路线并访问两点之间的所有点？

Answer 1

你想多了。通过三个中间节点只有六 (3*2*1) 条可能路径。只需全部检查即可。

对于较大的实例，您可以将问题减少到 TSP如下:

如果s是起始节点，t是最终节点，在s和t之间添加一条零权重边 和 s 与每个其他节点之间以及 t 与每个其他节点之间的无限重边。

这个问题是 NP-hard 问题，但是经过了非常深入的研究。您可以探索大量精确和近似算法。