Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Dijkstra's Algorithm
public class DijkstraSP
{
private double[] distTo; // distTo[v] = distance of shortest s->v path
private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path
private IndexMinPQ<Double> pq; // priority queue of vertices
public DijkstraSP( EdgeWeightedDigraph G, int s )
{
for ( DirectedEdge e : G.edges() )
{
if ( e.weight() < 0 )
throw new IllegalArgumentException( "edge " + e + " has negative weight" );
}
distTo = new double[ G.V() ];
edgeTo = new DirectedEdge[ G.V() ];
validateVertex( s );
for ( int v = 0; v < G.V(); v++ )
distTo[ v ] = Double.POSITIVE_INFINITY;
distTo[ s ] = 0.0;
pq = new IndexMinPQ<Double>( G.V() );
pq.insert( s, distTo[ s ] );
while ( !pq.isEmpty() )
{
int v = pq.delMin();
for ( DirectedEdge e : G.adj( v ) )
relax( e );
}
assert check( G, s );
}
private void relax( DirectedEdge e )
{
int v = e.from(), w = e.to();
if ( distTo[ w ] > distTo[ v ] + e.weight() )
{
distTo[ w ] = distTo[ v ] + e.weight();
edgeTo[ w ] = e;
if ( pq.contains( w ) ) pq.decreaseKey( w, distTo[ w ] );
else pq.insert( w, distTo[ w ] );
}
}
public double distTo( int v )
{
validateVertex( v );
return distTo[ v ];
}
public boolean hasPathTo( int v )
{
validateVertex( v );
return distTo[ v ] < Double.POSITIVE_INFINITY;
}
public Iterable<DirectedEdge> pathTo( int v )
{
validateVertex( v );
if ( !hasPathTo( v ) ) return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for ( DirectedEdge e = edgeTo[ v ]; e != null; e = edgeTo[ e.from() ] )
{
path.push( e );
}
return path;
}
private boolean check( EdgeWeightedDigraph G, int s )
{
for ( DirectedEdge e : G.edges() )
{
if ( e.weight() < 0 )
{
System.err.println( "negative edge weight detected" );
return false;
}
}
if ( distTo[ s ] != 0.0 || edgeTo[ s ] != null )
{
System.err.println( "distTo[s] and edgeTo[s] inconsistent" );
return false;
}
for ( int v = 0; v < G.V(); v++ )
{
if ( v == s ) continue;
if ( edgeTo[ v ] == null && distTo[ v ] != Double.POSITIVE_INFINITY )
{
System.err.println( "distTo[] and edgeTo[] inconsistent" );
return false;
}
}
for ( int v = 0; v < G.V(); v++ )
{
for ( DirectedEdge e : G.adj( v ) )
{
int w = e.to();
if ( distTo[ v ] + e.weight() < distTo[ w ] )
{
System.err.println( "edge " + e + " not relaxed" );
return false;
}
}
}
for ( int w = 0; w < G.V(); w++ )
{
if ( edgeTo[ w ] == null ) continue;
DirectedEdge e = edgeTo[ w ];
int v = e.from();
if ( w != e.to() ) return false;
if ( distTo[ v ] + e.weight() != distTo[ w ] )
{
System.err.println( "edge " + e + " on shortest path not tight" );
return false;
}
}
return true;
}
private void validateVertex( int v )
{
int V = distTo.length;
if ( v < 0 || v >= V )
throw new IllegalArgumentException( "vertex " + v + " is not between 0 and " + ( V - 1 ) );
}
public static void main( String[] args )
{
In in = new In( args[ 0 ] );
EdgeWeightedDigraph G = new EdgeWeightedDigraph( in );
int s = Integer.parseInt( args[ 1 ] );
DijkstraSP sp = new DijkstraSP( G, s );
for ( int t = 0; t < G.V(); t++ )
{
if ( sp.hasPathTo( t ) )
{
StdOut.printf( "%d to %d (%.2f) ", s, t, sp.distTo( t ) );
for ( DirectedEdge e : sp.pathTo( t ) )
{
StdOut.print( e + " " );
}
StdOut.println();
} else {
StdOut.printf( "%d to %d no path\n", s, t );
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.