Did you know that with a high level of probability, your car navigation device uses a variation of Shortest Path First (SPF) algorithm when guiding you home? And you in your car are in fact like a data packet inside IP datagram – travelling over hops via the shortest path to your destination?
Dutch computer scientist Edsger Dijkstra has invented SPF algorithm which is commonly used in network routing, such as by Open Shortest Path First (OSPF) protocol. OSPF is probably mostly-used interior gateway protocol, known to every network engineer.
SPF algorithm also served as a base for road planning engines, with the following noticeable differences:
- With computer network, each “node” is a physical box with its own SPF database: that’s the router. With road planning, nodes are virtual instances (called vertices in Graph theory) and contain no intelligence: the tool has the central database of nodes and edges connecting them.
- This means that in a stable computer network, all paths are pre-calculated, and each node (router) is instantly prepared to send your packet to the next hop. In road planning, once you ask for the best path, it needs to be calculated on the fly, start to end. Given the much bigger scale of roads, it can be very time and resource consuming process, especially if this planning is offered as a service from some central platform.
- While computer networks are typically interested only in the fastest delivery of a packet, they (in case of OSPF) would take into account the network bandwidth only. Road planners need to be more flexible: they will offer you the choice of shortest or fastest roads, or those bypassing highways, etc.
This led to the further development of SPF algorithms in attempt to minimize the time and resources consumed by calculations. We do not see these features in network routing:
- Bidirectional search: when search algorithm is applied simultaneously from source to destination and backwards. It is approximately 2 times faster than original Dijkstra algorighm.
- Pre-processing calculations were used in ALT and Geometric Pruning algorithms, delivering 10-20 times faster performance.
- Multi-level approach: when travelling from one city to the other the largest part of the road will be fixed on a highway, regardless of the exact position of the source and destination. Multi-level optimization feature takes this fact into account. It also relies on pre-processing and can deliver up to 2000 times faster performance.
As demonstrated in , a lot of focus is given to narrowing down the list of possibilities that the engine must search through while looking for the best path.
A – search area of original Dijkstra algorithm. B – A* algorithm. C – ALT algorithm.
So when you drive next time and hear “recalculating road to destination…” you can guess what is happening inside your navigator device.
Enjoy your driving!
Alex Mavrin, CCIE #7846
Visit http://www.apteriks.com and use FREE ONLINE tools for network professionals.
 Dijkstra algorithm
 Graph theory
 Shortest path problem
 Computing the Shortest Path: A* Search Meets Graph Theory