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.