Dijkstra的算法带有’必须通过’节点

我正在尝试实现Dijkstra的算法，该算法可以找到起始节点和结束节点之间的最短路径。 在到达终端节点之前，有一些“必须通过”的中间节点（多于一个），例如2或3必须通过必须在到达终端节点之前通过的节点。

如果我有一个必须通过节点，我找到的解决方案是找到从必须传递节点到目的地的两个不同路径，并从必须传递节点到启动节点。

我没有想法如何实现这样的算法。 有什么建议么？

谢谢。

List closestPathFromOrigin = null; double maxD = Double.POSITIVE_INFINITY; double _distance = 0; int temp1 = 0; List referencePath = new ArrayList(); boolean check = false; Node startNode = null; public List recursion(ArrayList points, ArrayList intermediatePoints) { if (!check) { System.out.println("--- DATA ---"); System.out.println("Intermediate points: " + intermediatePoints); System.out.println("points: " + points.get(0).lat + " " + points.get(1).lat); System.out.println("--Find the nearest intermediate point from the start point of driver--"); startNode = points.get(0); System.out.println("Start point of driver: " + startNode.lat + " " + startNode.lon); for (int i = 0; i < intermediatePoints.size(); i++) { List _path = dijkstra(startNode, intermediatePoints.get(i)); _distance = 0; for (int j = 0; j < _path.size() - 1; j++) { _distance += calculateDistance(_path.get(j), _path.get(j + 1)); } if (_distance  recursion, Yes -> stop"); if (!intermediatePoints.isEmpty()) { System.out.println("Recursion!!! with new data of: intermediatePoints: " + intermediatePoints); recursion(points, intermediatePoints); } else { System.out.println("Stop"); return referencePath; } } else { System.out.println("Recursion: startNode: " + startNode.lat + " " + startNode.lon); for (int i = 0; i  1) { System.out.println("From the new start point to the next nearest intermediate points if more than one points"); List _path = dijkstra(startNode, intermediatePoints.get(i)); _distance = 0; for (int j = 0; j < _path.size() - 1; j++) { _distance += calculateDistance(_path.get(j), _path.get(j + 1)); } if (_distance < maxD) { maxD = _distance; closestPathFromOrigin = _path; temp1 = i; } referencePath.addAll(closestPathFromOrigin); startNode = intermediatePoints.get(temp1); check = true; intermediatePoints.remove(intermediatePoints.get(temp1)); if (!intermediatePoints.isEmpty()) { recursion(points, intermediatePoints); } else { return referencePath; } } else { System.out.println("From the new start point to the next nearest intermediate points if just one point"); List _path = dijkstra(startNode, intermediatePoints.get(i)); //Collections.reverse(_path); referencePath.addAll(_path); } if (i == intermediatePoints.size() - 1) { System.out.println("Last Entry in intermediate points - find path to destination: " + points.get(1).lat + " " + intermediatePoints.get(i)); //List _path1 = dijkstra(points.get(1), intermediatePoints.get(i)); List _path1 = dijkstra(intermediatePoints.get(i), points.get(1)); Collections.reverse(_path1); referencePath.addAll(_path1); // referencePath.addAll(_path2); } } } return referencePath; } 

Answer 1

这是旅行商问题的概括。 TSP出现的情况是所有顶点都是“必须通过”的。

找到每对必须通过顶点之间的最短路径，从源到每个必须通过的顶点，以及从每个必须通过的顶点到接收器。 然后使用着名的O（n 2 ^ n）动态编程算法为TSP找到满足约束条件的源到源的最短路径; 这里n将是两个加上必须通过顶点的数量。

Answer 2

通过查找必须包含节点和两个（结束和开始）节点之间的最短路径。 表格图，然后运行最短路径算法（Dijkstra的算法）。 开始和结束节点将是相同的。

Answer 3

不幸的是，这个问题被简化为TSP所以不要期望多项式解决方案，但如果没有中间节点很小，那么你可以这样快速地做到这样：

1. 尝试每个节点序列访问可能。
2. 说你有s-> a-> b-> c-> d
3. 然后使用dijkstra评估min（s，d）+ min（d，a）+ min（c，d）
4. 最小距离的序列就是你的答案。

时间复杂度： O(k!*ElogV)其中k不是必须通过节点