Finding shortest path using Dijkstra’s algorithm and weighed directed graph

One of the first known uses of shortest path algorithms in technology was in telephony in the 1950’s. The problem was in finding alternate routing in case shortest route became blocked. In today’s world shortest path algorithms are used in plethora of applications. You can find them when calculating driving directions, airline travel routing, network communications, linguistics, social networks – they all use graphs to represent relationships between object.

In this particular post, I wanted to implement a weighed directed graph data structure. Because of its properties, weighed digraph is commonly used in mapping applications. I will use this graph in conjunction with the well-known Dijkstra’s algorithm to find shortest path between two points on a map. In order to do this, I will map intersection points on a small section of city map, then calculate shortest distance between those sets of points using our algorithm. Finally, I will use Google Maps driving directions on the same point sets to validate our experiment.

Continue reading “Finding shortest path using Dijkstra’s algorithm and weighed directed graph” »