JGraphT - Finding path with BreadthFirstIterator

Question

Here is the code to traverse the graph with BreathFirstIterator:

public class GraphTest {

    public static void main(String[] args) {
        DirectedGraph<Integer, DefaultEdge> graph = 
            new DefaultDirectedGraph <Integer, DefaultEdge>(DefaultEdge.class);

        graph.addVertex(7);
        graph.addVertex(4);
        graph.addVertex(9);
        graph.addVertex(3);
        graph.addVertex(2);
        graph.addVertex(5);


        graph.addEdge(7, 4);
        graph.addEdge(7, 9);
        graph.addEdge(9, 3);
        graph.addEdge(3, 2);
        graph.addEdge(3, 5);

        GraphIterator<Integer, DefaultEdge> iterator = 
                new BreadthFirstIterator<Integer, DefaultEdge>(graph);
        while (iterator.hasNext()) {
            System.out.println( iterator.next() );
        }
    }
}

As expected, the code prints out the list of all visited vertexes: 7,4,9,3,2,5. My problem is - I don't know how can I use this API to obtain a path with removed backtracks of algorithm. For example, for path from 7 to 2, it would output 7->9->3->2, and not just the list of visited vertexes. Stopping it after reaching the destination is obsiously not enough. Have anyone already solved this issue?

Answer 1

It is possible to get the shortest path between two vertices with DijkstraShortestPath.findPathBetween. It provides an implementation of Dijkstra's shortest path algorithm using ClosestFirstIterator. If there is no such path, it will return null.

Sample code:

DirectedGraph<Integer, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);

graph.addVertex(7);
graph.addVertex(4);
graph.addVertex(9);
graph.addVertex(3);
graph.addVertex(2);
graph.addVertex(5);

graph.addEdge(7, 4);
graph.addEdge(7, 9);
graph.addEdge(9, 3);
graph.addEdge(3, 2);
graph.addEdge(3, 5);

List<DefaultEdge> path = DijkstraShortestPath.findPathBetween(graph, 7, 2);
System.out.println(path); // prints [(7 : 9), (9 : 3), (3 : 2)]