Package org.goplanit.algorithms.shortest

Class ShortestPathDijkstra

  • All Implemented Interfaces:
    ShortestPathAllToOne, ShortestPathOneToAll
    public class ShortestPathDijkstra
extends ShortestPathGeneralised
implements ShortestPathOneToAll, ShortestPathAllToOne
    Dijkstra's shortest path algorithm Dijkstra's shortest path is a one-to-all (or all-to-one) implementation of the shortest path algorithm based on the generalized costs on each link segment (edge). The costs should be provided upon instantiation and are reused whenever an execution conditional on the chosen source/destination node is performed. In its current form, it assumes a macroscopic network and macroscopic link segments to operate on
    Author:
    markr

    • Field Detail

      • shortestEdgeSegmentOfVertex

        protected EdgeSegment[] shortestEdgeSegmentOfVertex
        Track incoming edge segment that is shortest for each vertex in this array

      • isShorterPredicate

        protected static final BiPredicate<Double,​Double> isShorterPredicate
        predicate for Dijkstra where shortest means less cost than existing cost, so only cheaper paths overwrite an existing shortest path to a node

    • Constructor Detail

      • ShortestPathDijkstra

        public ShortestPathDijkstra​(double[] edgeSegmentCosts,
                            int numberOfVertices)
        Constructor for an edge cost based Dijkstra algorithm for finding shortest paths.
        Parameters:
        edgeSegmentCosts - edge segment costs both physical and virtual
        numberOfVertices - Vertices, both nodes and centroids

    • Method Detail

      • execute

        public ShortestPathResult execute​(ShortestSearchType searchType,
                                  DirectedVertex startVertex)
        Execute shortest path search based on given search direction and start vertex
        Parameters:
        searchType - to use
        startVertex - to use
        Returns:
        results of shortest path search, if something went wrong null is returned

      • executeOneToAll

        public ShortestPathResult executeOneToAll​(DirectedVertex currentOrigin)
        Construct shortest paths from source node to all other nodes in the network based on directed LinkSegment edges
        Specified by:
        executeOneToAll in interface ShortestPathOneToAll
        Parameters:
        currentOrigin - origin vertex of source node
        Returns:
        shortest path result that can be used to extract paths

      • executeAllToOne

        public ShortestPathResult executeAllToOne​(DirectedVertex currentDestination)
        Construct shortest paths from all nodes to a single sink node in the network based on directed Link segment edges
        Specified by:
        executeAllToOne in interface ShortestPathAllToOne
        Parameters:
        currentDestination - destination vertex
        Returns:
        shortest path result that can be used to extract paths