Graphs and paths - Data Structures and Problem Solving Using Java - page 546

1 /**
2 * Single-source unweighted shortest-path algorithm.
3 */
4 public void unweighted( String startName )
5 {
6 clearAll( );
7
8 Vertex start = vertexMap.get( startName );
9 if( start == null )
10 throw new NoSuchElementException( "Start vertex not found" );
11
12 Queue<Vertex> q = new LinkedList<Vertex>( );
13 q.add( start ); start.dist = 0;
14
15 while( !q.isEmpty( ) )
16 {
17 Vertex v = q.remove( );
18
19 for( Edge e : v.adj )
20 {
21 Vertex w = e.dest;
22
23 if( w.dist == INFINITY )
24 {
25 w.dist = v.dist + 1;
26 w.prev = v;
27 q.add( w );
28 }
29 }
30 }
31 }

figure 14.22
The unweighted shortest-path algorithm, using breadth-first search

14.3.1 theory: dijkstra's algorithm

The positive-weighted, shortest-path problem is solved in much the same way
as the unweighted problem. However, because of the edge costs, a few things
change. The following issues must be examined:

Dijkstra's algorithm
is used to solve the
positive-weighted
shortest-path
problem.

1. How do we adjust D w ?

2. How do we find the vertex v for the eyeball to visit?