Ehump20
March 15th, 2007, 09:47 AM
public void unweighted( String startName )
{
clearAll( );
Vertex start = vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
Queue<Vertex> q = new LinkedList<Vertex>( );
q.add( start ); start.dist = 0;
while( !q.isEmpty( ) )
{
Vertex v = q.remove( );
for( Edge e : v.adj )
{
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.add( w );
}
}
}
}
For the unweighted shortest path algorithm, how would you change this code so that it searches for the minimum-cost vertex as a sequential scan of the vertex table? Thanks.
{
clearAll( );
Vertex start = vertexMap.get( startName );
if( start == null )
throw new NoSuchElementException( "Start vertex not found" );
Queue<Vertex> q = new LinkedList<Vertex>( );
q.add( start ); start.dist = 0;
while( !q.isEmpty( ) )
{
Vertex v = q.remove( );
for( Edge e : v.adj )
{
Vertex w = e.dest;
if( w.dist == INFINITY )
{
w.dist = v.dist + 1;
w.prev = v;
q.add( w );
}
}
}
}
For the unweighted shortest path algorithm, how would you change this code so that it searches for the minimum-cost vertex as a sequential scan of the vertex table? Thanks.