[ Data Structures with Java ] Section 25.4 : Shortest-Path Algorithm

Preface :
Transportation companies and communication networks use graphs to describe links between hubs in their systems. To optimize customer service and the flow of cargo or data, these system often need to determine the shortest-path length between two points (vertices). An algorithm, called the shortest-path algorithm, takes a specified vs. For each vertex v in the graph that is reachable from vs, the algorithm determines the length of a shortest path connecting vs to v. Vertices that are not reachable from vs have path length infinity (∞). For each reachable vertex, the algorithm provides both the length of the path and parent references so that the path of vertices can be constructed.
We can use the design of the breadth-first search to find shortest paths. The algorithm begins at a starting vertex sVertex and then proceeds to visit its neighbors (path length 1 from sVertex) followed by vertices with successively larger path lengths. it fans out from sVertex along paths of adjacent vertices until it visits all vertices reachable from sVertex. In order to determine the path length from sVertex to a vertex v, we need to modify bfs() so each vertex maintains a record of its parent and its path length from sVertex. The JGraph class provides methods that allow the programmer to associate two fields of information with a vertex. One field identifies the parent of a vertex and the other field is an integer dataValue associated with the vertex. The method initData() prepares a graph for the application of an optimization algorithm by assigning a representation for ∞ to each dataValue field of the graph vertices.

- Update class JGraph to have below APIs :

view plaincopy to clipboardprint?

1. public class JGraph implements Graph{  
2.     private HashMap> pathTable; // To record the path information according to each vertex in graph.  
3. ...  
4.     /** 
5.      * BD :  
6.      *   Assigns the dataValue field of each vertex to INFINITE 
7.      */  
8.     public void initData() {  
9.         Iterator iter = pathTable.keySet().iterator();  
10.         while(iter.hasNext()) {  
11.             T key = iter.next();  
12.             PathBean pb = pathTable.get(key);  
13.             if(pb!=null) {  
14.                 pb.dataValue = PathBean.INFINITE;  
15.                 pb.parent = null;  
16.                 pathTable.put(key, pb);  
17.             }  
18.         }  
19.     }  
20.       
21.     /** 
22.      * BD : 
23.      *   Returns the parent of vertex vertex. If vertex is not a graph vertex, throws IllegalArgumentException 
24.      */  
25.     public T getParent(T vertex) {  
26.         if(!vertexTable.containsKey(vertex)) throw new java.lang.IllegalArgumentException("getParent(): Vertices "+vertex+" doesn't exist");  
27.         PathBean pb = pathTable.get(vertex);  
28.         if(pb!=null) return pb.parent;  
29.         return null;  
30.     }  
31.       
32.     /** 
33.      * BD : 
34.      *   Returns the integer data value associated with vertex sVertex. If sVertex is not a graph vertex, 
35.      *   throws IllegalArgumentException 
36.      */  
37.     public int getData(T sVertex) {  
38.         if(vertexTable.containsKey(sVertex)) {  
39.             PathBean pb = pathTable.get(sVertex);  
40.             if(pb==null) {  
41.                 return PathBean.INFINITE;             
42.             }  
43.             return pb.dataValue;  
44.         }  
45.         throw new java.lang.IllegalArgumentException("setData(): Vertices "+sVertex+" doesn't exist");  
46.     }  
47.       
48.     /** 
49.      * BD : 
50.      *   Sets the integer data value associated with vertex sVertex and returns the previous value. 
51.      *   If sVertex is not a graph vertex, throws IllegalArgumentException. 
52.      */  
53.     public int setData(T sVertex, int data) {  
54.         if(vertexTable.containsKey(sVertex)) {  
55.             PathBean pb = pathTable.get(sVertex);  
56.             if(pb==null) {  
57.                 pb = new PathBean();                 
58.             }  
59.             int tmpData = pb.dataValue;  
60.             pb.dataValue = data;  
61.             pathTable.put(sVertex, pb);  
62.             return tmpData;  
63.         }   
64.         throw new java.lang.IllegalArgumentException("setData(): Vertices "+sVertex+" doesn't exist");  
65.     }  
66.       
67.     /** 
68.      * BD : 
69.      *   Assigns the parent of vertex sVertex to be pVertex and returns the previous parent. If sVertex or 
70.      *   pVertex is not a graph vertex, throws IllegalArgumentException. 
71.      */  
72.     public T setParent(T sVertex, T pVertex){  
73.         if(vertexTable.containsKey(sVertex) && vertexTable.containsKey(pVertex)) {  
74.             PathBean pb = pathTable.get(sVertex);  
75.             if(pb==null) {  
76.                 pb = new PathBean();  
77.                   
78.             }   
79.             T tmpParent = pb.parent;  
80.             pb.parent = pVertex;  
81.             pathTable.put(sVertex, pb);  
82.             return tmpParent;  
83.         }  
84.         throw new java.lang.IllegalArgumentException("setParent(): Vertices "+sVertex+" or "+pVertex+" doesn't exist");  
85.     }  
86. ...  
87. }  

The shortest-path algorithm is an iterative process that uses a queue to store the vertices. At each step, the algorithm pops an element from the queue. This becomes the current vertex and provides access to an adjacency list that may include unvisited neighbors. Before pushing an unvisited adjacent vertex on the queue, the algorithm assigns values to parent and dataValue fields of the adjacent vertex. The current vertex is the parent and the dataValue is the path length from the starting vertex to the adjacent vertex. This is simply one more than the path length to the current vertex. The iterative process terminates when the queue is empty. The dataValue field of each vertex is the shortest-path length and its parent field allows us to backtrack along a path of parents to list the vertices in the shortest path. A proof that this algorithm does yield the shortest path is difficult and beyond the scope of the book. The interested reader should consult a book on the theory of algorithms.
Let us see how all of this plays out for the graph in below figure. We will find the shortest-path from vertex C to each of the reachable vertices in the graph :


Start the algorithm with sVertex=C. In the vertex, set the dataValue (path length) to 0 and make sVertex its own parent. Initialize the queue by adding C as the first element. In the figure, we represent a queue element with the name of the vertex and use subscripts for the pathLenght and parent. Columns in the table identify the order in which vertices are visited and the current path length from vertex C :
Step1:

Pop C from the queue. Identify the two neighbors, E and F, and set their colors to GRAY (discovered). Their path lengths are 1 = 0 + 1, and C is their parent. Add the neighbors to the queue. (Figure-a)

Step2:

Pop E from the queue. Its neighbor, vertex D, is not discovered and so we add it to the queue with path length 2 from C and with E as its parent.

Step3:

Pop F from the queue. F has no discovered neighbors, so simply proceed to Step4.

Step4:

Pop D from the queue. Add the undiscovered neighbor B to the queue with path length 3 and parent D.

Step5:

Pop B from the queue. The neighbor E has been discovered. In fact, it was visited in Step2. No new element is added to the queue. The algorithm terminates because the queue is empty.

At the conclusion of the algorithm, the data value for a vertex is the shortest-path length from starting vertex C. In addition, we can build the shortest-path. For instance, look at vertex B. The parent reference field indicates that the parent of B is D. We can backtrack to the starting vertex using the fact that P(B)=D, P(D)=E and P(E)=C. The shortest path from C to B is [C, E, D, E].

Implementing the shortestPath() Method :
The implementation of the static method shortestPath() includes arguments for the graph and the starting vertex. A queue holds the vertices that the algorithm discovers. After the pushing the starting vertex onto the queue, a look continues until the algorithm finds the shortest-path length to all vertices that are reachable from the starting vertex. This occurs when the queue is empty. The path length can be accessed using the getData() method.

- Method shortestPath() in class JGraph :

view plaincopy to clipboardprint?

1. /** 
2. * BD : 
3. *  Use the breadth-first traversal algorithm to determine the minimum number of edges 
4. *  in any path from sVertex to all vertices in the graph reachable from sVertex; upton 
5. *  return, the dataValue field of each vertex in g is either the shortest path length to  
6. *  vertex or is INFINITY if the vertex was not reachable from sVertex; 
7. *  call path(g, sVertex, v) to find the shortest path from sVertex to v 
8. */  
9. public static void shortestPath(JGraph g, T sVertex) {  
10.     if(!g.containsVertex(sVertex)) throw new java.lang.IllegalArgumentException("shortestPath(): Vertices "+sVertex+" doesn't exist");  
11.     LinkedQueue visitQueue = new LinkedQueue();  
12.     HashMap verticesColor = new HashMap();  
13.     Iterator iter = g.vertexSet().iterator();  
14.     while(iter.hasNext()) verticesColor.put(iter.next(), VertexColor.WHITE);  
15.     g.initData();  
16.     g.setData(sVertex, 0);  
17.     g.setParent(sVertex, sVertex);  
18.       
19.     T currVertex, neighborVertex;  
20.     Iterator edgeIter;  
21.     int currentLength=PathBean.INFINITE;  
22.     visitQueue.push(sVertex);  
23.     while(!visitQueue.isEmpty()) {  
24.         currVertex = visitQueue.pop();  
25.         edgeIter = g.getNeighbors(currVertex).iterator();  
26.         currentLength = g.getData(currVertex);  
27.         while(edgeIter.hasNext()) {  
28.             neighborVertex = edgeIter.next();  
29.             if(verticesColor.get(neighborVertex).equals(VertexColor.WHITE)) {  
30.                 verticesColor.put(neighborVertex, VertexColor.GRAY);  
31.                 g.setParent(neighborVertex, currVertex);  
32.                 g.setData(neighborVertex, currentLength+1);  
33.                 visitQueue.push(neighborVertex);  
34.             }  
35.         }  
36.     }  
37. }  

The shortest-path algorithm stores parent references that identify the parent of each vertex on a path of shortest length. The method path() builds the path. The arguments includes the graph and two vertices specifying the starting and ending vertices. The method assumes that an optimum path method has been called and that appropriate parent references are defined. The return value is a linked list of vertices designating the path from the starting vertex to the ending vertex :

- Method path() in class JGraph :

view plaincopy to clipboardprint?

1. public static  LinkedList path(JGraph g, T sVertex, T eVertex) {  
2.     T currentVertex = eVertex;  
3.     LinkedList path = new LinkedList();  
4.     if(g.getData(eVertex) == PathBean.INFINITE) return path;  
5.     while(!currentVertex.equals(sVertex)) {  
6.         path.addFirst(currentVertex);  
7.         currentVertex = g.getParent(currentVertex);  
8.     }  
9.     path.addFirst(sVertex);  
10.     return path;  
11. }  

- Running-Time Analysis
The shortest-path algorithm simply uses the breadth-first search. There is additional O(V) overhead to initialize the dataValue for each vertex. With the breadth-first search having running time O(V+E), the total running time for the shortest path is O(V+E).

Supplement :
* Wiki : Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) such that the sum of the weights of its constituent edges is minimized. An example is finding the quickest way to get from one location to another on a road map; in this case, the vertices represent locations and the edges represent segments of road and are weighted by the time needed to travel that segment.

* [ 資料結構 小學堂 ] 圖形結構 : 圖形最短路徑 (單點對全部頂點)

在一個有向圖形 G=(V,E), G 中的每一個邊都有一個比例常數 W(Weight) 與之對應, 如果想求 G 圖形中某一點V0 到其他頂點的最少 W 總和之值, 這類問題就稱為最短路徑問題 (The shortest path problem).

This message was edited 16 times. Last update was at 15/03/2011 11:05:37