Dijkstra算法中的“必经节点”问题

Question

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

如果我有一个必经节点，我找到的解决方案是从必经节点到目的地和从必经节点到起始节点找到两条不同的路径。

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

谢谢。

List<Node> closestPathFromOrigin = null;

double maxD = Double.POSITIVE_INFINITY;
double _distance = 0;
int temp1 = 0;
List<Node> referencePath = new ArrayList<>();
boolean check = false;
Node startNode = null;

public List<Node> recursion(ArrayList<Node> points, ArrayList<Node> 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<Node> _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;
            }
        }
        System.out.println("NearestPoint from driver's origin: " + intermediatePoints.get(temp1));

        referencePath.addAll(closestPathFromOrigin);
        startNode = intermediatePoints.get(temp1);
        System.out.println("New StartNode: the nearestPoint from driver's origin: " + startNode.lat + " " + startNode.lon);
        check = true;
        intermediatePoints.remove(intermediatePoints.get(temp1));
        System.out.println("New Intermediate points: " + intermediatePoints);
        System.out.println("Intermediate points empty? No -> 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 < intermediatePoints.size(); i++) {
            if (intermediatePoints.size() > 1) {
                System.out.println("From the new start point to the next nearest intermediate points if more than one points");
                List<Node> _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<Node> _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<Node> _path1 = dijkstra(points.get(1), intermediatePoints.get(i));
                List<Node> _path1 = dijkstra(intermediatePoints.get(i), points.get(1));

                Collections.reverse(_path1);
                referencePath.addAll(_path1);
               //  referencePath.addAll(_path2);
            }
        }
    }
    return referencePath;
}

- user3778610

---

如果您必须通过节点，则需要多次运行Dijkstra算法。从起点到中间点1，再从中间点1到中间点2等依此类推，直到到达终点，使用相同的逻辑。请注意，不同的路径可能会共用相同的中间节点。 - user2858650

我尝试着通过多次调用Dijkstra算法来实现递归方法。首先从起始节点找到最近的点。我只是添加了上面的代码。 - user3778610

这是一个有向图还是无向图？ - Alpenglow

是一个有向图。 - user3778610

@DanK他没有说明必须通过节点有一个顺序。你认为他如何能有效地找到最优顺序呢？ - G. Bach

Answer 1

这是旅行商问题的一般化。当所有顶点都是“必经之路”时，会出现TSP。

找到每对必经顶点之间的最短路径，从源到每个必经顶点，并从每个必经顶点到汇点。然后使用著名的O(n 2^n) TSP动态规划算法来找到从源到满足您约束条件的汇点的最短路径；这里n将是必经顶点数加二。

- tmyklebu

---

非常感谢。您是否有教程链接，以便了解如何实现TSP算法？ - user3778610

Answer 2

很不幸，这个问题被缩小到TSP，所以不要期望有多项式解决方案，但如果中间节点的数量很少，则可以像以下这样快速处理：

1. 尝试访问可能的每个节点序列。
2. 假设您有s->a->b->c->d
3. 然后使用Dijkstra评估min(s,d)+min(d,a)+min(c,d)
4. 具有最小距离的序列是您的答案。

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

- Vikram Bhat

Answer 3

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

- kafee651