org.rollerjm.graph
Class Dijkstra

java.lang.Object
  |
  +--org.rollerjm.graph.Dijkstra

public class Dijkstra

extends java.lang.Object

Title: graphs

Description: implementation of the Dijkstra's algorithm to search for the shortest distance in a weighted graph

Copyright: Copyright (c) 2002

Company:

Version:

1.0

Author:

Jean-Michel Garnier

Nested Class Summary

class

Dijkstra.PriorityQueue Title: graphs

Field Summary

private java.util.HashSet	determinedVerticesSet the set of determines vertices V
private IGraph	graph The graph on which we apply the algorithm
private static int	INFINITE the INFINITE, the maximum weight should be < to this value
private java.util.HashMap	predecessorsMap the result map of predecessors of the shortest path from a start vertex after running the algorithm
private Dijkstra.PriorityQueue	remainingVertices the list of remaining vertices Q
private java.util.HashMap	shortestPathMap the result map of the shortest path distances from a start vertex after running the algorithm

Constructor Summary

Dijkstra(IGraph graph)

Method Summary

private Path	buildShortestPath(java.lang.Object start, java.lang.Object destination) used the predecessorsMap to build the shortest path from a start vertex to a destination vertex
private void	checkVertexExist(java.lang.Object vertex)
Path	getShortestPath(java.lang.Object start, java.lang.Object destination)
private int	getShortestPathFromStart(java.lang.Object vertex)
int	getShortestWeightDistance(java.lang.Object start, java.lang.Object destination)
private void	relax(java.lang.Object u)
private void	runAlgorihtm(java.lang.Object startVertex, java.lang.Object destinationVertex) Run the algorihtm see http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html for details
private void	setShortestPathFromStart(java.lang.Object vertex, int path)

Methods inherited from class java.lang.Object

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

Field Detail

INFINITE

private static final int INFINITE

the INFINITE, the maximum weight should be < to this value

See Also:

Constant Field Values

graph

private IGraph graph

The graph on which we apply the algorithm

determinedVerticesSet

private java.util.HashSet determinedVerticesSet

the set of determines vertices V

remainingVertices

private Dijkstra.PriorityQueue remainingVertices

the list of remaining vertices Q

shortestPathMap

private java.util.HashMap shortestPathMap

the result map of the shortest path distances from a start vertex after running the algorithm

predecessorsMap

private java.util.HashMap predecessorsMap

the result map of predecessors of the shortest path from a start vertex after running the algorithm

Constructor Detail

Dijkstra

public Dijkstra(IGraph graph)

Parameters:

graph -

Method Detail

runAlgorihtm

private void runAlgorihtm(java.lang.Object startVertex,
                          java.lang.Object destinationVertex)

Run the algorihtm see http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html for details

Parameters:

startVertex -

destinationVertex -

relax

private void relax(java.lang.Object u)

Parameters:

u - vertex whose adjacents vertices should be relaxed

getShortestPathFromStart

private int getShortestPathFromStart(java.lang.Object vertex)

Parameters:

vertex -

Returns:

int after running the algorithm with a start vertex, return the distance of the shortet path (to go to param vertex). INFINITE if path does not exist

setShortestPathFromStart

private void setShortestPathFromStart(java.lang.Object vertex,
                                      int path)

Parameters:

vertex -

path -

getShortestWeightDistance

public int getShortestWeightDistance(java.lang.Object start,
                                     java.lang.Object destination)

Parameters:

start -

destination -

Returns:

int weight distance of the shortest path or Dijkstra. INFINITE if path does not exist

getShortestPath

public Path getShortestPath(java.lang.Object start,
                            java.lang.Object destination)

Parameters:

start -

destination -

Returns:

Path of the shortest path or Dijkstra. Empty path if the path does not exist

buildShortestPath

private Path buildShortestPath(java.lang.Object start,
                               java.lang.Object destination)

used the predecessorsMap to build the shortest path from a start vertex to a destination vertex

Parameters:

start -

destination -

Returns:

Path

checkVertexExist

private void checkVertexExist(java.lang.Object vertex)

Parameters:

vertex -