Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| xmlgraphics-commons 2.2
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.xmlgraphics.util.dijkstra
Class DijkstraAlgorithm

    java.lang.Object
      org.apache.xmlgraphics.util.dijkstra.DijkstraAlgorithm

    public class DijkstraAlgorithm

extends Object

This is an implementation of Dijkstra's algorithm to find the shortest path for a directed graph with non-negative edge weights.

See Also:
  WikiPedia on Dijkstra's Algorithm

Field Summary
`static int` | `INFINITE` Infinity value for distances.

Constructor Summary
`DijkstraAlgorithm(EdgeDirectory edgeDirectory)` Main Constructor.

Method Summary
`void` | `execute(Vertex start, Vertex destination)` Run Dijkstra's shortest path algorithm.
`protected Iterator` | `getDestinations(Vertex origin)` Returns an iterator over all valid destinations for a given vertex.
`int` | `getLowestPenalty(Vertex vertex)` Returns the lowest penalty from the start point to a given vertex.
`protected int` | `getPenalty(Vertex start, Vertex end)` Returns the penalty between two vertices.
`Vertex` | `getPredecessor(Vertex vertex)` Returns the vertex's predecessor on the shortest path.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### INFINITE

    public static final int INFINITE

  Infinity value for distances.

  See Also:
    Constant Field Values

Constructor Detail

### DijkstraAlgorithm

    public DijkstraAlgorithm(EdgeDirectory edgeDirectory)

  Main Constructor.

  Parameters:
    `edgeDirectory` - the edge directory this instance should work on

Method Detail

### getPenalty

    protected int getPenalty(Vertex start,
                             Vertex end)

  Returns the penalty between two vertices.

  Parameters:
    `start` - the start vertex
    `end` - the end vertex
  Returns:
    the penalty between two vertices, or 0 if no single edge between the two vertices exists.

### getDestinations

    protected Iterator getDestinations(Vertex origin)

  Returns an iterator over all valid destinations for a given vertex.

  Parameters:
    `origin` - the origin from which to search for destinations
  Returns:
    the iterator over all valid destinations for a given vertex

### execute

    public void execute(Vertex start,
                        Vertex destination)

  Run Dijkstra's shortest path algorithm. After this method is finished you can use `getPredecessor(Vertex)` to reconstruct the best/shortest path starting from the destination backwards.

  Parameters:
    `start` - the starting vertex
    `destination` - the destination vertex.

### getLowestPenalty

    public int getLowestPenalty(Vertex vertex)

  Returns the lowest penalty from the start point to a given vertex.

  Parameters:
    `vertex` - the vertex
  Returns:
    the lowest penalty or `INFINITE` if there is no route to the destination.

### getPredecessor

    public Vertex getPredecessor(Vertex vertex)

  Returns the vertex's predecessor on the shortest path.

  Parameters:
    `vertex` - the vertex for which to find the predecessor
  Returns:
    the vertex's predecessor on the shortest path, or `null` if there is no route to the destination.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| xmlgraphics-commons 2.2
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright 1999-2017 The Apache Software Foundation. All Rights Reserved.