Package algs

Class Dijkstra

java.lang.Object

algs.Dijkstra

public class Dijkstra
extends Object

Dijkstra's algorithm.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static interface	Dijkstra.EdgeWeight	Functional interface for edge weights.

Constructor Summary

Constructors

Constructor	Description
Dijkstra(Graph g)	Create an instance of Dijkstra's algorithm for graph g.
Dijkstra(Graph g, Dijkstra.EdgeWeight w)	Create an instance of Dijkstra's algorithm to compute shortest paths from s to all other vertices in g.

Method Summary

Modifier and Type	Method	Description
double	getDist(Vertex f)	Get the length of the shortest path from vertex s to vertex f.
Iterable<Edge>	getPathEdges(Vertex f)	Get the edges on the shortest path from vertex s to vertex f.
Iterable<Vertex>	getPathVertices(Vertex f)	Get the vertices on the shortest path from vertex s to vertex f.
void	init(Vertex s)	Initialize the algorithm.
void	run()	Compute shortest paths from s to all vertices.
void	run(Vertex f)	Compute shortest path from vertex s to vertex f.

Methods inherited from class java.lang.Object

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

Constructor Details

Dijkstra

public Dijkstra(Graph g)

Create an instance of Dijkstra's algorithm for graph g. Assumes that the weight for edge e is (Double)e.getObject().

Parameters:

g - the graph

Dijkstra

public Dijkstra(Graph g,
 Dijkstra.EdgeWeight w)

Create an instance of Dijkstra's algorithm to compute shortest paths from s to all other vertices in g.

Parameters:

g - the graph

w - function taking an Edge and returning the weight for the edge (as a double)

Method Details

init

public void init(Vertex s)

Initialize the algorithm.

Parameters:

s - starting vertex

run

public void run()

Compute shortest paths from s to all vertices.

run

public void run(Vertex f)

Compute shortest path from vertex s to vertex f.

Parameters:

f - finish vertex; if null, compute the shortest path to all vertices

getPathVertices

public Iterable<Vertex> getPathVertices(Vertex f)

Get the vertices on the shortest path from vertex s to vertex f.

Parameters:

f - finish vertex

Returns:

the vertices on the shortest path from vertex s to vertex f

getPathEdges

public Iterable<Edge> getPathEdges(Vertex f)

Get the edges on the shortest path from vertex s to vertex f.

Parameters:

f - finish vertex

Returns:

the edges on the shortest path from vertex s to vertex f

getDist

public double getDist(Vertex f)

Get the length of the shortest path from vertex s to vertex f.

Parameters:

f - finish vertex

Returns:

the length of the shortest path from vertex s to vertex f