Introduction

Obviously to be able to find the shortest distance or cost between any two nodes in a graph is a very useful thing.

Dijkstra’s algorithm to find the shortest path between two points. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor’s distance if smaller.

I find it more intuitive if I think in terms of driving from one place to another. I look at the map, and compare the different routes in distance and traffic (plus toll). I choose the route with the shortest distance (unless traffic is bad).

Dijkstra’s algorithm

Dijkstra’s method has two steps:

1. Update estimates
2. Choose next node

Initially all distances are labeled as \(\infinity\), except the starting node.

Reference

Videos

How Dijkstra’s Algorithm Works Graphs: Dijkstra’s Minimal Spanning Tree and Dijkstra’s Shortest Path