lu.cs.co.demo
Class Dijkstra

java.lang.Object
  |
  +--lu.cs.co.demo.Dijkstra

public class Dijkstra

extends Object

A class for shortest paths in graphs and digraphs. After the constructor ShortestPath(G,s,t) has been invoked, the method findPath() returns the shortest path from s to t.

More generally, after the constructor ShortestPath(G,s) has been invoked, a shortest paths from s to every vertex v reachable from s is known and can be found by findPath(v). As an example, the following code finds a shortest path from Vertex u to Vertex v in Graph G:

 ShortestPath SP= new ShortestPath(G,u,v);
 Path P= (SP.isReachable()) ? SP.findPath() : null;
 

Bug: Overestimates the path length from the source to itself.

Constructor Summary

Dijkstra(Graph G, Vertex s)

Dijkstra(Graph G, Vertex s, Vertex t)

Method Summary

int	dist(Vertex v) Find the distance to a vertex.
Path	findPath() Find a shortest path from the source to the sink.
Path	findPath(Vertex v) Find the shortest path from the source to a vertex.
boolean	isReachable()
boolean	isReachable(Vertex v)
static void	main(String[] args) Throwaway demo method: read in a source, sink, and graph and print the shortest path.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Dijkstra

public Dijkstra(Graph G,
                Vertex s)

Dijkstra

public Dijkstra(Graph G,
                Vertex s,
                Vertex t)

Method Detail

dist

public int dist(Vertex v)

Find the distance to a vertex. Assumes the vertex to be reachable

Returns:

the shortest distance from the source to v.

isReachable

public boolean isReachable(Vertex v)

Returns:

true iff the distance from the source to v is known.

isReachable

public boolean isReachable()

Returns:

true iff the distance from the source to the sink is known

findPath

public Path findPath(Vertex v)

Find the shortest path from the source to a vertex. Assumes that such a path exists.

findPath

public Path findPath()

Find a shortest path from the source to the sink. Assumes that the sink is reachable from the source.

main

public static void main(String[] args)

Throwaway demo method: read in a source, sink, and graph and print the shortest path. For example,

java lu.cs.co.demo.Dijkstra chaos order word 0 3 4

finds a shortest path from chaos to order in the 5757 vertex graph Words(0,3,4). The output looks like this:

 
 graph "Length 72 simple path in Words(0,3,4)" {
   chaos -- chaps -- claps -- clams -- coals -- docks -- hocks -- 
   locks -- pocks -- rocks -- soaks -- spans -- trams -- prams -- 
   orals -- ovals -- quals -- quais -- pubis -- pubes -- nudes -- 
   nuder -- order;
 }