YouTipGraph Theory Short Path
## Breadth-First Traversal and Shortest Path
Breadth-First Traversal starts from a certain vertex v, first visits this node and marks it as visited, then sequentially visits all unvisited adjacent nodes {vi,..,vj} of vertex v and marks them as visited. Then, it repeats the visit method of node v for each node in {vi,...,vj} 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 if the queue is empty.
* (2) If the queue is not empty, dequeue the first element, enqueue all unvisited nodes associated with this element, and mark these nodes as visited.
* (3) If the queue is empty, it means all nodes have been traversed in breadth-first order.
The image below shows, on the right in blue, the order of traversing nodes starting from 0. Below it 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 perform traversal using breadth-first traversal and find the shortest path. Based on the code from the previous section, we add a global variable `ord` array to record the order of nodes in the path. `ord` represents the order of node `i` in the path. The constructor is adjusted accordingly; when traversing adjacent nodes, for each unvisited node accessed, we record the distance with `ord = ord + 1`. The time complexity of breadth-first traversal for 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 `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=false;
from=-1;
ord=-1;
}
this.s= s;
// Shortest path algorithm for undirected graphs, performs breadth-first traversal of the entire graph starting from s
LinkedList q =new LinkedList();
q.push( s );
visited=true;
ord=0;
while(!q.isEmpty()){
int v = q.pop();
for(int i : G.adj(v))
if(!visited){
q.push(i);
visited=true;
from= v;
ord= ord+1;
}
}
}
...
View 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 =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=false;
from=-1;
ord=-1;
}
this.s= s;
// Shortest path algorithm for undirected graphs, performs breadth-first traversal of the entire graph starting from s
LinkedList q =new LinkedList();
q.push( s );
visited=true;
ord=0;
while(!q.isEmpty()){
int v = q.pop();
for(int i : G.adj(v))
if(!visited){
q.push(i);
visited=true;
from= v;
ord= ord+1;
}
}
}
// Queries if there is a path from point s to point w
public boolean hasPath(int w){
assert w >=0&& w < G.V();
return visited;
}
// Queries the path from point s to point w, stored in vec
public Vector path(int w){
assert hasPath(w);
Stack s =new Stack();
// Reverse lookup the path from s to w using the from array, storing it in the stack
int p = w;
while( p !=-1){
s.push(p);
p = from;
}
// Pop elements from the stack sequentially to obtain the path from s to w in order
Vector res =new Vector();
while(!s.empty())
res.add( s.pop());
return res;
}
// Prints the path from point s to point w
public void showPath(int w){
assert hasPath(w);
Vector vec = path(w);
for(int i =0; i ");
}
}
// Views 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;
}
}