logo-header

 
 

Dijkstra algorithm

The dijkstra alogorithm determines the minimum impedance of the routes through a network/graph of nodes and links with given link-impedance for each combination of given origins and destinations.

 

Dijkstra functions in the GeoDMS

In the GeoDMS a family of functions is implemented using this algorithm to find the minimum impedance in a network/graph.These functions are used calculate shortes paths in directed/bidirectional graphs, OD matrices, multiple impedances, with or without filters.

Origin/destination combinations (further: od-pairs) can be filterd in two ways:

  • by setting a maximum impedance (per origin) and/or
  • a maximum amount of visited destination mass per origin.

Furthermore, the user can specify the production of additional results per origin, destination, link, or od-pair such as:

  • an alternative link impedance measure, to be aggregated over the found routes
  • interaction results: trip generation, distribution, and network flow assignment, following Alonso's Theory of Movements.

Origin and destination zones can be specified as a set of startPoints or endPoints that relate to the network nodes with an optional additional Impedance per startPoint and/or endPoint.

When no od-pair related output is requested, the memory usage remains proportional to the memory size of the given network and calculation time remains proportional to the number of actually visited nodes (plus some initialization time proportional to the size of the network).

documentation

Documentation on the family of dijkstra functions can be found in the section as well as in our Wiki, http://wiki.objectvision.nl/index.php/Dijkstra_functions


OBJECT VISION BV
Vrije Universiteit
De Boelelaan 1085
1081 HV Amsterdam
The Netherlands

tel: +31 (0)20 598 9083
fax:+31 (0)20 598 9904