Breadth-first traversal and shortest path
Breadth-first traversal starts from a vertex v, first visits this node and marks it as visited, then sequentially visits all unvisited neighbors {vi,..,vj} of node v and marks them as visited, then for each node in {vi,...,vj} repeats the visiting method of node v until all nodes have been visited.
We can divide it into three steps:
- (1) Use an auxiliary queue q. First enqueue vertex v and mark it as visited, then loop to check whether the queue is empty.
- (2) If the queue is not empty, take out the first element of the queue, enqueue all unvisited nodes associated with this element, and mark these nodes as visited.
- (3) If the queue is empty, it means that all nodes have been traversed in breadth-first order.
As shown in the figure below, the blue on the right indicates the order of traversing nodes starting from 0, and the part below records the distance from 0. It can be seen that breadth-first traversal can find the shortest path in an unweighted graph.
The following code demonstrates how to complete traversal using breadth-first traversal and query the shortest path. Based on the code from the previous section, we add a global variable, the ord array, to record the order of nodes in the path. ord[i] represents the order of node i in the path. At the same time, the constructor is adjusted accordingly: when traversing adjacent nodes, each time an unvisited node is visited, the distance is recorded as ord[i] = ord[v] + 1. The time complexity of breadth-first traversal using an adjacency list is O(V+E), and the time complexity using an adjacency matrix is O(V^2).
// Constructor, pathfinding algorithm, finds paths from point s to other points in graph
public ShortestPath(Graph graph, int s){
// Algorithm initialization
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// Undirected graph shortest path algorithm: starting from s, perform breadth-first traversal of the entire graph
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
...
Check the shortest path length from point s to point w; if w is unreachable from s, return -1.
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
...
Java example code
Source code package download:Download
src/example/graph/ShortestPath.java file code:
import example.graph.read.Graph;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Vector;
/**
* Breadth-First Traversal and Shortest Path
*/
public class ShortestPath {
// 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;
// Record the order of nodes in the path. ord[i] represents the order of node i in the path.
private int[] ord;
// Constructor, pathfinding algorithm, finds paths from point s to other points in graph
public ShortestPath(Graph graph, int s){
// Algorithm initialization
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// Undirected graph shortest path algorithm: starting from s, perform breadth-first traversal of the entire graph
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
// Query whether there is a path from node s to node w
public 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
public 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
public 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(" -> ");
}
}
// Check the shortest path length from point s to point w
// If the path from s to w is unreachable, return -1
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
}