Package dsa

Class Dijkstra

java.lang.Object
dsa.Dijkstra
All Implemented Interfaces:
Paths
public class Dijkstra extends Object implements Paths
An immutable data type to determine the shortest paths from a fixed source vertex to every other vertex in an edge-weighted digraph.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Dijkstra(EdgeWeightedDiGraph G, int s)
    Determines the shortest paths from the source vertex s to every other vertex in the edge-weighted digraph G.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    distTo(int v)
    Returns the shortest distance between a designated source vertex and vertex v, or infinity.
    boolean
    hasPathTo(int v)
    Returns true if there is a path between a designated source vertex and vertex * v, and false otherwise.
    static void
    main(String[] args)
    Unit tests the data type.
    Iterable<Integer>
    pathTo(int v)
    Returns a path between a designated source vertex and vertex v, or null.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • Dijkstra

      public Dijkstra(EdgeWeightedDiGraph G, int s)
      Determines the shortest paths from the source vertex s to every other vertex in the edge-weighted digraph G.
      Parameters:
      G - the edge-weighted digraph.
      s - the source vertex.

  • Method Details

    • hasPathTo

      public boolean hasPathTo(int v)
      Returns true if there is a path between a designated source vertex and vertex * v, and false otherwise.
      Specified by:
      hasPathTo in interface Paths
      Parameters:
      v - the vertex.
      Returns:
      true if there is a path between a designated source vertex and vertex v, and false otherwise.

    • pathTo

      public Iterable<Integer> pathTo(int v)
      Returns a path between a designated source vertex and vertex v, or null.
      Specified by:
      pathTo in interface Paths
      Parameters:
      v - the vertex.
      Returns:
      a path between a designated source vertex and vertex v, or null.

    • distTo

      public double distTo(int v)
      Returns the shortest distance between a designated source vertex and vertex v, or infinity.
      Specified by:
      distTo in interface Paths
      Parameters:
      v - the vertex.
      Returns:
      the shortest distance between a designated source vertex and vertex v, or infinity.

    • main

      public static void main(String[] args)
      Unit tests the data type.
      Parameters:
      args - the command-line arguments.