How to find a shortest path that must pass through a predefined subset of vertices

Question

I wanna get the shortest path with specifying vertices that must be passed. I asked chatGPT to solve it and I got a code but a library doesn't exist: org.jgrapht.alg.shortestpath.ConstrainedShortestPathAlgorithm What is the instead library? Or what is correct code?

import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.shortestpath.ConstrainedShortestPathAlgorithm;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Test {

    public static void main(String[] args) {
        // Create a simple weighted graph
        Graph<String, DefaultWeightedEdge> graph = new SimpleWeightedGraph<>(DefaultWeightedEdge.class);

        // Add vertices
        List<String> vertices = Arrays.asList("A", "B", "C", "D", "E", "F");
        for (String vertex : vertices)
            graph.addVertex(vertex);

        // Add edges with weights
        graph.setEdgeWeight(graph.addEdge("A", "B"), 3);
        graph.setEdgeWeight(graph.addEdge("A", "C"), 1);
        graph.setEdgeWeight(graph.addEdge("B", "C"), 1);
        graph.setEdgeWeight(graph.addEdge("B", "D"), 2);
        graph.setEdgeWeight(graph.addEdge("C", "D"), 2);
        graph.setEdgeWeight(graph.addEdge("C", "E"), 4);
        graph.setEdgeWeight(graph.addEdge("D", "F"), 3);
        graph.setEdgeWeight(graph.addEdge("E", "F"), 2);

        // Set constraints to pass through vertices "B" and "D"
        Set<String> constraints = new HashSet<>(Arrays.asList("B", "D"));

        // Find the shortest path while passing through the specified constraints
        ConstrainedShortestPathAlgorithm<String, DefaultWeightedEdge> cspa = new ConstrainedShortestPathAlgorithm<>(
                graph);
        GraphPath<String, DefaultWeightedEdge> shortestPath = cspa.getShortestPath("A", "F",
                new VertexSetConstraint<>(constraints));

        // Print the shortest path
        System.out.println("Shortest path while passing through vertices " + constraints + ": "
                + shortestPath.getVertexList() + ", weight=" + shortestPath.getWeight());
    }
}

I'm using jgrapht-1.5.1. I checked folders but the library doesn't exist.

Answer 1

JGraphT does not have a class ConstrainedShortestPathAlgorithm, perhaps in the future. I assume that you are looking for a shortest path that (i) connects your source and target vertices and (ii) a pre-specified subset of 'obligatory' vertices are visited along that path, but not necessary in that order. So in your example, a shortest path could be A-D-E-B-F. In this path, vertices B and D are visited, but not in this order.

Claim: this problem is NP-hard. Proof: Pick a traveling salesman problem instance, add 2 vertices, say S and T, and connect them to all other vertices with zero cost. Then find a shortest path from S to T, that must pass through all other vertices in the graph. The resulting problem would solve your TSP problem.

Since your problem is NP-hard, depending on the graph it would make solving this problem quite challenging. Nevertheless, to solve your problem, here's 2 alternative solution approaches:

1. Create a new, undirected graph, say G', containing your source vertex S, target vertex T and all obligatory vertices. Next, add edge (S,T) with weight 0. For every other pair of vertices i and j in G', compute the shortest path from i to j in your original graph G using any shortest path algorithm (e.g. Dijkstra's algorithm). If such path exists, add edge (i,j) to G' and set its weight equal to the length of the shortest path. Omit edge (i,j) if no such shortest path exists. Finally, solve a Traveling Salesman Problem on the resulting graph G'. This will provide you with an optimal order in which you have to visit your vertices. As a final step, you would have to reconstruct a solution in terms of the original graph G. As per example, imagine that your TSP tour would be: A-D-B-F. The optimal solution would then be a concatenation of the shortest paths: P(A,D) - P(D,B) - P(B-F), where P(i,j) is the shortest path from i to j in G.

2. A heuristic but easy way to solve your problem is to first order your set of obligatory vertices, and then find a shortest path between them. This works particularly well on map-based graphs. Imagine you want to compute a shortest-path roadtrip that starts in Amsterdam and ends Rome. Along the way you want to visit Paris and Brussels. In this example, {Paris,Brussels} are your obligatory vertices. You could simply order the set of obligatory vertices, e.g. 'go to the nearest city first'. From Amsterdam, the nearest city in your obligatory set is Brussels. The second nearest city is Paris. So you would want to visit Brussels first, and then Paris. You could then compute the shortest path Amsterdam to Brussels, add to that the shortest path from Brussels to Paris, and finally add to that the shortest path from Paris to Rome. For geographical networks this could work very well.

Note: both approaches can be implemented in JGraphT. The first approach requires a shortest path algorithm and an algorithm to solve TSP problems, the 2nd approach only uses shortest path algorithms. JGraphT has both. W.r.t. TSP algorithms, JGraphT has both exact and heuristic algorithms. The scalability of JGraphT's exact TSP algorithm is limited; if you would need to solve really large instances, you'd be better of using the Concorde TSP solver.