Class DijkstraShortestPath<V,W>

java.lang.Object
org.episteme.core.mathematics.discrete.DijkstraShortestPath<V,W>
public class DijkstraShortestPath<V,W> extends Object
Dijkstra's algorithm for finding the shortest paths in a weighted graph.

Computes shortest paths from a single source vertex to all other vertices (or a specific target) in a graph with non-negative edge weights.

*

Reference:
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269-271.

Since:
1.0
Author:
Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

  • Constructor Details

    • DijkstraShortestPath

      public DijkstraShortestPath(WeightedGraph<V,W> graph, GraphWeightAdapter<W> adapter)
      Creates a new Dijkstra algorithm instance.
      Parameters:
      graph - the weighted graph
      adapter - the weight adapter for operations

  • Method Details

    • ofReal

      public static <V> DijkstraShortestPath<V,Real> ofReal(WeightedGraph<V,Real> graph)
      Creates a new Dijkstra algorithm instance for Real weights.
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the weighted graph with Real weights
      Returns:
      a new instance

    • ofDouble

      public static <V> DijkstraShortestPath<V,Double> ofDouble(WeightedGraph<V,Double> graph)
      Creates a new Dijkstra algorithm instance for Double weights.
      Type Parameters:
      V - the vertex type
      Parameters:
      graph - the weighted graph with Double weights
      Returns:
      a new instance

    • findPath

      public List<V> findPath(V source, V target)
      Computes the shortest path from source to target.
      Parameters:
      source - the starting vertex
      target - the destination vertex
      Returns:
      the list of vertices in the path, or empty list if no path exists

    • getDistance

      public W getDistance(V source, V target)
      Computes the length of the shortest path from source to target.
      Parameters:
      source - the starting vertex
      target - the destination vertex
      Returns:
      the distance, or null if no path exists

    • computeAllDistances

      public Map<V,W> computeAllDistances(V source)
      Computes shortest paths from source to all reachable vertices.
      Parameters:
      source - the starting vertex
      Returns:
      map of vertex to shortest distance from source