Pathfinding Algorithm

Graph pathfinding algorithms can also be implemented using depth-first search (DFS) to find paths in a graph from a starting point ( s ) to other points. In the previous section's implementation class, a global variable from array is added to record the paths, where from[i] indicates the previous node of ( i ) on the path being searched.

First, the constructor initializes the initial conditions for the pathfinding algorithm, initializing from = new int[G.V()] and setting default values in a loop: the visited array is all false, and the from array is all -1, followed by recursive DFS processing for the starting node.

...
// Constructor, pathfinding algorithm, finding paths in graph from point s to others
public Path(Graph graph, int s){
    // Algorithm initialization
    G = graph;
    assert s >= 0 && s < G.V();
    visited = new boolean[G.V()];
    from = new int[G.V()];
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        from[i] = -1;
    }
    this.s = s;
    // Pathfinding algorithm
    dfs(s);
}
...

To determine if there is a path from point ( s ) to point ( w ), simply query the corresponding value in the visited array.

...
boolean hasPath(int w){
    assert w >= 0 && w < G.V();
    return visited[w];
}
...

To get the specific path from point ( s ) to point ( w ), we implement it using the path method. First, check if they are connected by calling the hasPath method. As per the constructor, we can trace back all paths using the from array.

...
Vector<Integer> path(int w){
    assert hasPath(w) ;
    Stack<Integer> s = new Stack<Integer>();
    // Trace back the path from s to w using the from array, storing it in a stack
    int p = w;
    while( p != -1 ){
        s.push(p);
        p = from[p];
    }
    // Retrieve elements from the stack to get the sequential path from s to w
    Vector<Integer> res = new Vector<Integer>();
    while( !s.empty() )
        res.add( s.pop() );
    return res;
}
...

Java Example Code

Source Code Download: Download

src/tutorialpro/graph/Path.java File Code:

package tutorialpro.graph;

import tutorialpro.graph.read.Graph;

import java.util.Stack;
import java.util.Vector;

/**
 * Pathfinding
 */
public class Path {
    // Graph reference
    private Graph G;
    // Starting point
    private int s;
    // Record whether nodes have been visited during DFS
    private boolean[] visited;
    // Record paths, from[i] indicates the previous node of i on the searched path
    private int[] from;

    // Depth-first traversal of the graph
    private void dfs( int v ){
        visited[v] = true;
        for( int i : G.adj(v) )
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
    }

    // Constructor, pathfinding algorithm, finding paths in graph from point s to others
    public Path(Graph graph, int s){
        // Algorithm initialization
        G = graph;
        assert s >= 0 && s < G.V();

visited = new boolean[G.V()];
from = new int[G.V()];
for(int i = 0; i < G.V(); i++) {
    visited[i] = false;
    from[i] = -1;
}
this.s = s;
// Pathfinding algorithm
dfs(s);
}

// Check if there is a path from s to w
boolean hasPath(int w) {
    assert w >= 0 && w < G.V();
    return visited[w];
}

// Find the path from s to w and store it in vec
Vector<Integer> path(int w) {

    assert hasPath(w);

    Stack<Integer> s = new Stack<Integer>();
    // Reverse lookup the path from s to w using the from array and store it in the stack
    int p = w;
    while(p != -1) {
        s.push(p);
        p = from[p];
    }

    // Retrieve elements from the stack to get the sequential path from s to w
    Vector<Integer> res = new Vector<Integer>();
    while(!s.empty())
        res.add(s.pop());

    return res;
}

// Print the path from s to w
void showPath(int w) {

    assert hasPath(w);

    Vector<Integer> vec = path(w);
    for(int i = 0; i < vec.size(); i++) {
        System.out.print(vec.elementAt(i));
        if(i == vec.size() - 1)
            System.out.println();
        else
            System.out.print(" -> ");
    }
}
}