Breadth-First Search and Shortest Path

Breadth-First Search (BFS) starts from a vertex v, visits this node, and marks it as visited. Then, it sequentially visits all unvisited adjacent nodes {vi,...,vj} of v, marks them as visited, and repeats the process for each node in {vi,...,vj}, until all nodes have been visited.

The process can be divided into three steps:

• (1) Use an auxiliary queue q, initially enqueue vertex v, mark it as visited, and then loop to check if the queue is empty.

• (2) If the queue is not empty, dequeue the first element, enqueue all its unvisited adjacent nodes, mark them as visited.

• (3) If the queue is empty, it means all nodes have been visited in breadth-first order.

The diagram below shows the traversal order starting from 0 in blue on the right, and the distances from 0 recorded below. It demonstrates that BFS can find the shortest path in an unweighted graph.

The following code demonstrates how to perform a breadth-first traversal and find the shortest path. We add a global variable ord array to record the order of nodes in the path. ord[i] represents the order of node i in the path. The constructor is adjusted accordingly, recording the distance with ord[i] = ord[v] + 1 for each unvisited node visited. The time complexity for BFS with an adjacency list is O(V+E), and for an adjacency matrix, it 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;
    // Unweighted graph shortest path algorithm, BFS traversal starting from s
    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;
            }
    }
}
...

To check the shortest path length from point s to point w, if s is not reachable to w, return -1.

...
public int length(int w){
    assert w >= 0 && w < G.V();
    return ord[w];
}
...

Java Example Code

Source Code Download: Download

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

package tutorialpro.graph;

import tutorialpro.graph.read.Graph;

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

/**
 * Breadth-First Search and Shortest Path
 */
public class ShortestPath {
    // Graph reference
    private Graph G;
    // Starting point
    private int s;
    // Record if nodes are visited during DFS
    private boolean[] visited;
    // Record path, from[i] indicates the previous node of i on the search path
    private int[] from;
    // Record the order of nodes in the path. ord[i] indicates the order of node i in the path.

private int[] ord;
// Constructor, pathfinding algorithm, finds paths from source s to other nodes 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 and performing a 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;
            }
    }
}

// Checks if there is a path from s to w
public boolean hasPath(int w) {
    assert w >= 0 && w < G.V();
    return visited[w];
}
// Retrieves the path from s to w and stores it in vec
public Vector<Integer> path(int w) {
    assert hasPath(w);
    Stack<Integer> s = new Stack<Integer>();
    // Reverse lookup of the path from s to w using the from array, stored in a stack
    int p = w;
    while (p != -1) {
        s.push(p);
        p = from[p];
    }

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

    return res;
}

// Prints the path from s to 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(" -> ");
    }
}
// Retrieves the shortest path length from s to w
// Returns -1 if s to w is not reachable
public int length(int w) {
    assert w >= 0 && w < G.V();
    return ord[w];
}