Dijkstra's algorithm with "required" nodes

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

If I need to traverse a node, then the solution I found finds two different paths from the required traversal node to the destination and from there the node must traverse in order to start the node.

I don't understand how I can implement such an algorithm. Any suggestions?

Thank.

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 origin: " + intermediatePoints.get(temp1));

        referencePath.addAll(closestPathFromOrigin);
        startNode = intermediatePoints.get(temp1);
        System.out.println("New StartNode: the nearestPoint from driver 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;
}

      

+3


source to share


3 answers


This is a generalization of the traveling salesman problem. TSP appears when all vertices are "required".



Find the shortest paths between each pair of required vertices, from the source to each overflow vertex, and from each transition vertex to the shell. Then use the famous O (n 2 ^ n) dynamic programming algorithm for TSP to find the shortest path from the source to the ceiling that satisfies your constraints; here n will be equal to two plus the number of transition vertices.

+4


source


Finding the shortest path between should include node and two (end and start) node. Shape graph, then follow the shortest path algo (Dijkstra's algorithm). The start and end nodes will be the same.



+1


source


Unfortunately this problem boils down to TSP, so don't expect a polynomial solution, but if there is no intermediate node then you can do it fast enough as shown below: -

  • try every sequence of nodes you can visit.
  • say you have s-> a-> b-> c-> d
  • then evaluate min (s, d) + min (d, a) + min (c, d) using dijkstra
  • the sequence that has the minimum distance is your answer.

Time complexity: O(k!*ElogV)

where k should not go through the nodes

+1


source







All Articles