Pathfinding Algorithm
The graph pathfinding algorithm can also be implemented using depth-first search (DFS), finding paths from a starting point s to other points in the graph. In the implementation class from the previous subsection, add a global variable `from` array to record paths; `from[i]` represents the previous node of `i` on the found path.
First, the constructor initializes the initial conditions of the pathfinding algorithm,from = new int[G.V()]andfrom = new int[G.V()]and sets default values in a loop: all values in the `visited` array are `false`, and all values in the `from` array are `-1`. Then, recursive DFS processing is performed on the starting node.
// Constructor, pathfinding algorithm, finds paths from point s to other points in graph
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 whether there is a path from point s to point w, just check the corresponding value in the `visited` array.
boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
...
To obtain the specific path from s to w, we implement it using the `path` method. First, determine whether they are connected by calling the `hasPath` method. As can be seen from the constructor, all paths can be found simply by tracing upward through the `from` array.
Vector<Integer> path(int w){
assert hasPath(w) ;
Stack<Integer> s = new Stack<Integer>();
// Through the from array, trace back the path from s to w and store it in the stack
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// Take elements out of the stack one by one to get the ordered 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 package download:Download
Code in src/example/graph/Path.java:
import example.graph.read.Graph;
import java.util.Stack;
import java.util.Vector;
/**
* Pathfinding
*/
public class Path {
// Reference to the graph
private Graph G;
// Starting point
private int s;
// Record whether a node is visited during DFS
private boolean[] visited;
// Record the path; from[i] represents the previous node of i on the search 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, finds paths from point s to other points in graph
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);
}
// Query whether there is a path from node s to node w
boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
// Query the path from node s to node w and store it in vec
Vector<Integer> path(int w){
assert hasPath(w) ;
Stack<Integer> s = new Stack<Integer>();
// Through the from array, trace back the path from s to w and store it in the stack
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// Take elements out of the stack one by one to get the ordered path from s to w
Vector<Integer> res = new Vector<Integer>();
while( !s.empty() )
res.add( s.pop() );
return res;
}
// Print the path from node s to node 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(" -> ");
}
}
}