David Turner, April 7, 2011

OTP Internals (beta version)

Dijkstra's algorithm

Dijkstra's algorithm

Initialize empty priority queue of vertices
     class FibHeap
Initialize empty shortest path tree
     class ShortestPathTree
Priority is total cost to get to vertex
Initialize empty closed set
Put the start vertex on the queue
   While there are any vertices in the queue
       Remove the lowest (=closest to start) vertex from the queue
       "Settle" it:
       If the lowest vertex is the destination
             Done algorithm
       Put the lowest vertex in the closed set
       For each outgoing edge from lowest vertex -- GraphVertex.getOutgoing()
           If destination not in closed set:
               Traverse edge Edge.traverse()
               Update cost to destination vertex in SPT class SPTVertex
               Update position of destination vertex in queue
   If queue is empty
       Path not found

Next: Some additional complexities
Previous

Copyright © 2011, OpenPlans. Licensed under CC BY-SA