Skip to content

Dijkstra’s Routing Algorithm

One of the most commonly used routing algorithms is Dijkstra’s algorithm. Dijkstra’s algorithm finds the shortest path between two nodes by building a shortest-path tree, and stopping once the destination node has been reached. Normally in routing applications, Dijkstra’s algorithm is used to find the shortest route between 2 locations. This is the case with Map Suite Routing’s built-in Dijkstra routing algorithm. However, there may be instances where you may want to find the shortest path from a single source node to several destination nodes. With a few small modifications, you can use Dijkstra’s algorithm in order to efficiently get multiple route results from a single location to multiple destinations.

Usually with Dijkstra’s algorithm you would pass in a single source node (point A) and a single destination node (point B). The algorithm would find the shortest path between point A and each intermediate node, until it eventually finds the shortest path between point A and point B.

routing 1

Dijkstra algorithm routing from Point A to Point B. The green lines represent the nodes traversed by the routing, while the red line is the final route

If desired, you can get the shortest path from a source node (point A) to multiple destination nodes (points B, C, D) by allowing the algorithm to continue building the shortest-path tree until all of the desired routes have been covered. Once this is done, you can get all of the desired routes, while only having to perform the routing once.

Routing2

Dijkstra routing with multiple destinations from the same source node at one time.

There are a few practical applications for this. For example, if you are solving a real-life Traveling Salesperson Problem, you may need to build a “distance matrix” of the distances between each set of points. Using this technique, you can avoid having to route from each point to each other point individually, saving a lot of time and processing re-traversing nodes multiple times.

Map Suite GIS Services Routing currently supports routing using multiple algorithms including A-Star, Dijkstra, and TSP routing algorithms. An API for this “multi-destination” routing will be added to Map Suite Routing later this year.

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *