Dijkstra算法与“必须通过”节点 [英] Dijkstra's algorithm with 'must-pass' nodes

问题描述

我想实现Dijkstra算法可以找到起始节点和终端节点之间的最短路径。在到达终点节点还是有一些必须通过之前到达终点节点必须通'的中间节点（不止​​一个），例如2或3必须通过节点。

如果我有一个必须通过节点的解决方案，我发现是找到两个不同路径的必经节点目标和必须通过节点启动节点。

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

感谢。

 名单，其中，节点＆GT; closestPathFromOrigin = NULL;

双MAXD = Double.POSITIVE_INFINITY;
双_distance = 0;
INT temp1中= 0;
名单＆LT;节点＆GT; referencePath =新的ArrayList＆LT;＆GT;（）;
布尔查= FALSE;
节点的StartNode = NULL;

公开名单＆LT;节点＆GT;递归（ArrayList的＆LT;节点＆GT;点，ArrayList的＆LT;节点＆GT; intermediatePoints）{

    如果（！检查）{
        的System.out.println（--- --- DATA）;
        的System.out.println（中间点+ intermediatePoints）;
        的System.out.println（分+ points.get（0）.lat ++ points.get（1）.lat）;
        的System.out.println（ - 查找的driver--起点最近的中间点）;
        的StartNode = points.get（0）;
        的System.out.println（起点司机：+ startNode.lat ++ startNode.lon）;
        的for（int i = 0; I＆LT; intermediatePoints.size（）;我++）{
            名单＆LT;节点＆GT; _path = Dijkstra算法（的StartNode，intermediatePoints.get（I））;
            _distance = 0;
            对于（INT J = 0; J＆LT; _path.size（） -  1; J ++）{
                _distance + = calculateDistance（_path.get（J），_path.get（J + 1））;
            }
            如果（_distance＆LT; MAXD）{
                MAXD = _distance;
                closestPathFromOrigin = _path;
                temp1中=我;
            }
        }
        的System.out.println（从驾驶员的来源NearestPoint：+ intermediatePoints.get（temp1中））;

        referencePath.addAll（closestPathFromOrigin）;
        的StartNode = intermediatePoints.get（temp1中）;
        的System.out.println（新的StartNode：从司机的起源nearestPoint：+ startNode.lat ++ startNode.lon）;
        检查=真;
        intermediatePoints.remove（intermediatePoints.get（temp1中））;
        的System.out.println（新中间点：+ intermediatePoints）;
        的System.out.println（？中间点空否 - ＆GT;递归，是 - ＆GT;停止）;
        如果（！intermediatePoints.isEmpty（））{
            的System.out.println（递归!!!与新的数据：intermediatePoints：+ intermediatePoints）;
            递归（分，intermediatePoints）;
        } 其他 {
            的System.out.println（停止）;
            返回referencePath;
        }
    } 其他 {
        的System.out.println（递归：的StartNode：+ startNode.lat ++ startNode.lon）;
        的for（int i = 0; I＆LT; intermediatePoints.size（）;我++）{
            如果（intermediatePoints.size（）→1）{
                的System.out.println（从新开始点到下一个最近的中间点，如果一个以上的点）;
                名单＆LT;节点＆GT; _path = Dijkstra算法（的StartNode，intermediatePoints.get（I））;
                _distance = 0;
                对于（INT J = 0; J＆LT; _path.size（） -  1; J ++）{
                    _distance + = calculateDistance（_path.get（J），_path.get（J + 1））;
                }
                如果（_distance＆LT; MAXD）{
                    MAXD = _distance;
                    closestPathFromOrigin = _path;
                    temp1中=我;
                }
                referencePath.addAll（closestPathFromOrigin）;
                的StartNode = intermediatePoints.get（temp1中）;
                检查=真;
                intermediatePoints.remove（intermediatePoints.get（temp1中））;
                如果（！intermediatePoints.isEmpty（））{
                    递归（分，intermediatePoints）;
                } 其他 {
                    返回referencePath;
                }
            } 其他 {
                的System.out.println（在新的起点到下一个最近的中间点，如果只是一个点）;
                名单＆LT;节点＆GT; _path = Dijkstra算法（的StartNode，intermediatePoints.get（I））;
                //Collections.reverse(_path）;
                referencePath.addAll（_path）;
            }
            如果（ⅰ== intermediatePoints.size（） -  1）{
                的System.out.println（最后一项的中间点 - 寻找到目的主机：+ points.get（1）.lat ++ intermediatePoints.get（一））;
                //名单，其中，节点＆GT; _path1 =迪杰斯特拉（points.get（1），intermediatePoints.get（ⅰ））;
                名单＆LT;节点＆GT; _path1 =迪杰斯特拉（intermediatePoints.get（i）中，points.get（1））;

                Collections.reverse（_path1）;
                referencePath.addAll（_path1）;
               // referencePath.addAll（_path2）;
            }
        }
    }
    返回referencePath;
}
 

解决方案

这是旅行商问题的推广。该TSP出现的情况下，所有的顶点都是必须通。

查找每对都必须通顶点之间的最短路径，从源头上每个人都必须通顶点，从每个人都必须通顶点向下沉。然后，使用著名的O（N 2 ^ n）的动态规划算法TSP找到从源点到汇满足您的约束条件的最短路径;这里的n将是二加必须通顶点的数量。

I am trying to implement Dijkstra's algorithm which can find the shortest path between the start node and the end node. Before reach the end node there are some 'must-pass' intermediate nodes (more than one) for example 2 or 3 must pass nodes which must pass before reach the end node.

If i have one must pass node the solution i found is find two different paths from the must pass node to destination and from must pass node to start node.

I am out of ideas how i can implement such an algorithm. Any suggestions?

Thanks.

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;
}

解决方案

This is a generalisation of the travelling salesman problem. The TSP comes up as the case where all vertices are "must-pass".

Find shortest paths between each pair of must-pass vertices, from the source to each must-pass vertex, and from each must-pass vertex to the sink. Then use the famous O(n 2^n) dynamic programming algorithm for TSP to find the shortest path from source to sink meeting your constraints; here n will be two plus the number of must-pass vertices.

这篇关于Dijkstra算法与“必须通过”节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！