Algorithm

Now that we've established the problem representation, let's discuss Dijkstra's algorithm. Dijkstra's requires the input graph to have only one source node. It also requires that all the edges in the graph have non-negative weights.

Suppose we are given a map such as the one below and wish to travel from city A to city F. In a simple graph like this, we can see that there are several paths to travel from A to F.

After a hard look, you'll realize that the path A -> C -> D -> F will give us the shortest path. But that required a lot of thought, and you most likely had to analyze every path one by one before coming to the conclusion.

But what if you have a more complicated graph with hundreds of cities? In such a case, you could use Dijkstra's algorithm. It makes this work easier by finding the distance values for the path for each unvisited node n. This distance value will be the shortest distance of that node n from the source node. This helps in determining the shortest path.