org.apache.xmlgraphics.util.dijkstra

## Class DijkstraAlgorithm

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

-     public class DijkstraAlgorithm
      extends java.lang.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

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `static int` | `INFINITE` Infinity value for distances.

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `DijkstraAlgorithm(EdgeDirectory edgeDirectory)` Main Constructor.

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `execute(Vertex start, Vertex destination)` Run Dijkstra's shortest path algorithm.
    `protected java.util.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 java.util.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.

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