Package org.matsim.core.router

Class Dijkstra

  • All Implemented Interfaces:
    LeastCostPathCalculator
    Direct Known Subclasses:
    AStarEuclidean, FastDijkstra, MultiNodeDijkstra
    public class Dijkstra
extends Object
implements LeastCostPathCalculator
    Implementation of Dijkstra's shortest-path algorithm on a time-dependent network with arbitrary non-negative cost functions (e.g. negative link cost are not allowed). So 'shortest' in our context actually means 'least-cost'.

    For every router, there exists a class which computes some preprocessing data and is passed to the router class constructor in order to accelerate the routing procedure. The one used for Dijkstra is PreProcessDijkstra.


    Code example:

    PreProcessDijkstra preProcessData = new PreProcessDijkstra();
    preProcessData.run(network);
    TravelCost costFunction = ...
    LeastCostPathCalculator routingAlgo = new Dijkstra(network, costFunction, preProcessData);
    routingAlgo.calcLeastCostPath(fromNode, toNode, startTime);

    If you don't want to preprocess the network, you can invoke Dijkstra as follows:

    LeastCostPathCalculator routingAlgo = new Dijkstra(network, costFunction);

    Important note

    This class is NOT thread-safe!
    Author:
    lnicolas, mrieser
    See Also:
    PreProcessDijkstra, AStarEuclidean, AStarLandmarks

    • Field Detail

      • network

        protected Network network
        The network on which we find routes.

      • timeFunction

        protected final TravelTime timeFunction
        The travel time calculator. Provides the travel time for each link and time step.

    • Constructor Detail

      • Dijkstra

        protected Dijkstra​(Network network,
                   TravelDisutility costFunction,
                   TravelTime timeFunction)
        Default constructor.
        Parameters:
        network - The network on which to route.
        costFunction - Determines the link cost defining the cheapest route.
        timeFunction - Determines the travel time on links.

      • Dijkstra

        protected Dijkstra​(Network network,
                   TravelDisutility costFunction,
                   TravelTime timeFunction,
                   PreProcessDijkstra preProcessData)
        Constructor.
        Parameters:
        network - The network on which to route.
        costFunction - Determines the link cost defining the cheapest route.
        timeFunction - Determines the travel time on each link.
        preProcessData - The pre processing data used during the routing phase.

    • Method Detail

      • constructPath

        protected LeastCostPathCalculator.Path constructPath​(Node fromNode,
                                                     Node toNode,
                                                     double startTime,
                                                     double arrivalTime)
        Constructs the path after the algorithm has been run.
        Parameters:
        fromNode - The node where the path starts.
        toNode - The node where the path ends.
        startTime - The time when the trip starts.

      • relaxNode

        protected void relaxNode​(Node outNode,
                         Node toNode,
                         RouterPriorityQueue<Node> pendingNodes)
        Expands the given Node in the routing algorithm; may be overridden in sub-classes.
        Parameters:
        outNode - The Node to be expanded.
        toNode - The target Node of the route.
        pendingNodes - The set of pending nodes so far.

      • addToPendingNodes

        protected boolean addToPendingNodes​(Link l,
                                    Node n,
                                    RouterPriorityQueue<Node> pendingNodes,
                                    double currTime,
                                    double currCost,
                                    Node toNode)
        Adds some parameters to the given Node then adds it to the set of pending nodes.
        Parameters:
        l - The link from which we came to this Node.
        n - The Node to add to the pending nodes.
        pendingNodes - The set of pending nodes.
        currTime - The time at which we started to traverse l.
        currCost - The cost at the time we started to traverse l.
        toNode - The target Node of the route.
        Returns:
        true if the node was added to the pending nodes, false otherwise (e.g. when the same node already has an earlier visiting time).

      • revisitNode

        protected void revisitNode​(Node n,
                           DijkstraNodeData data,
                           RouterPriorityQueue<Node> pendingNodes,
                           double time,
                           double cost,
                           Link outLink)
        Changes the position of the given Node n in the pendingNodes queue and updates its time and cost information.
        Parameters:
        n - The Node that is revisited.
        data - The data for n.
        pendingNodes - The nodes visited and not processed yet.
        time - The time of the visit of n.
        cost - The accumulated cost at the time of the visit of n.
        outLink - The link from which we came visiting n.

      • visitNode

        protected void visitNode​(Node n,
                         DijkstraNodeData data,
                         RouterPriorityQueue<Node> pendingNodes,
                         double time,
                         double cost,
                         Link outLink)
        Inserts the given Node n into the pendingNodes queue and updates its time and cost information.
        Parameters:
        n - The Node that is revisited.
        data - The data for n.
        pendingNodes - The nodes visited and not processed yet.
        time - The time of the visit of n.
        cost - The accumulated cost at the time of the visit of n.
        outLink - The node from which we came visiting n.

      • augmentIterationId

        protected void augmentIterationId()
        Augments the iterationID and checks whether the visited information in the nodes in the nodes have to be reset.

      • getIterationId

        protected int getIterationId()
        Returns:
        iterationID

      • getPriority

        protected double getPriority​(DijkstraNodeData data)
        The value used to sort the pending nodes during routing. This implementation compares the total effective travel cost to sort the nodes in the pending nodes queue during routing.

      • getData

        protected DijkstraNodeData getData​(Node n)
        Returns the data for the given node. Creates a new NodeData if none exists yet.
        Parameters:
        n - The Node for which to return the data.
        Returns:
        The data for the given Node