Why did Dijkstra cross the road? Cuz it was the shortest path!

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph, which as conceived by Edsger W. Dijkstra in 1956. The original version of the algorithm found the shortest path between two nodes, but the more common version found the shortest paths between a “source” node and all other nodes of a graph.

To create a graph, we use nodes or vertices, all of which are connected to one more nodes by paths or edges. Nodes are labeled arbitrarily and edges are given a cost value or weight. The idea is to start at one node and traverse other nodes at minimal costs.

So in this example, we start a node 1 and determine the minimum edge connected to node 1 (in this case, node 2). We say that node 1 has now been visited and node 2 is our current node. From node 2, we determine the minimum edge, which is node 7. As we traverse through a path, we sum the cost of all edges traverse. So to get node 7 from node 1, the cost of traversal was 5, and we constantly update the weight at each node.

Notice in the third image that we start at node 1 again. The total cost to traverse from node 7 to any other node would be greater than moving from node 1 to node 4, therefore, we traverse to node 4. This continues until all nodes have been traverse and we have created a minimum spanning path for all nodes starting from node 1.

A way to represent a graph of minimum spanning paths is to construct a min-heap. A min-heap is a tree of nodes where our starting node is the root node and the children nodes are those greater in value than its parent node.


Why do we care about finding the shortest path? Well, imagine you want to get to the Post Office, or the gym, from your current location. You could spend the same amount of time going your usual route, but after some experimentation, you may find a route that is faster. With Dijkstra’s algorithm, you can create a network of roads and determine minimal road length with any source node.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s