[Verse 1] Started with a graph, got nodes and weighted edges Need the shortest path, making algorithmic pledges Initialize the distance, set source node to zero All the others infinite, that's how we start this hero Priority queue ready, gonna track the smallest cost Greedy local choices, no efficiency is lost Edsger Dijkstra built this, back in fifty-nine Single source shortest path, every time it shines [Chorus] Distance, queue, and relax the edge Update neighbors, that's our pledge Mark it visited, never go back Shortest path is on the track Distance, queue, and relax the edge Greedy choice is our advantage Pop the minimum, spread the cost Optimal solution, never lost [Verse 2] Extract the minimum from the priority queue Current node selected, here's what we gotta do Check each neighbor's distance through this current node If it's shorter than before, update the road Relaxation process, that's the key technique Compare the distances, find the one that's sleek Add the edge weight to the current distance found If it's less than stored, new path has been crowned [Chorus] Distance, queue, and relax the edge Update neighbors, that's our pledge Mark it visited, never go back Shortest path is on the track Distance, queue, and relax the edge Greedy choice is our advantage Pop the minimum, spread the cost Optimal solution, never lost [Bridge] No negative weights allowed in this game Positive edges keep the algorithm's flame Time complexity big O of V squared With binary heap, V log V is declared Breadth-first spreading from the source node out Wave-like expansion, that's what it's about [Verse 3] Visited set grows with every iteration Unvisited shrinks through systematic elimination Previous pointers track the optimal route Backtrack from target when you want the pursuit Monotonic property keeps the distances true Once a node is visited, its distance won't renew Termination happens when the queue is empty Or target node is reached, algorithm's plenty [Chorus] Distance, queue, and relax the edge Update neighbors, that's our pledge Mark it visited, never go back Shortest path is on the track Distance, queue, and relax the edge Greedy choice is our advantage Pop the minimum, spread the cost Optimal solution, never lost [Outro] From GPS routing to network design Dijkstra's algorithm keeps the paths aligned Shortest tree spanning from a single source West coast algorithm with unstoppable force
← Distributed Systems Concepts - CAP theorem, eventual consistency, sharding strat | Dijkstra vs Other Path-Finding Algorithms →