[Verse 1] Started with a graph and nodes to explore Every path has weight, gotta find the score Shortest distance is the name of the game Edsger Dijkstra put us all on the flame Initialize the source to zero on sight Every other vertex set to infinite height Priority queue keeps the order tight Always pick the minimum, that's the light [Chorus] Relax the edges, update the cost Check every neighbor, nothing gets lost Distance plus weight, compare what you got If it's smaller then update the spot Queue it up, queue it up, mark it done Dijkstra's way till the algorithm's won No negative weights, that's the rule Shortest path finder, ultimate tool [Verse 2] Pull the minimum from the priority scene Mark it visited, keep the process clean Look at every neighbor that's still in queue Calculate the distance, see if it's new Current node distance plus the edge weight Compare to neighbor's current state If the sum is less than what they hold Update the distance, story retold [Chorus] Relax the edges, update the cost Check every neighbor, nothing gets lost Distance plus weight, compare what you got If it's smaller then update the spot Queue it up, queue it up, mark it done Dijkstra's way till the algorithm's won No negative weights, that's the rule Shortest path finder, ultimate tool [Bridge] Greedy choice at every single turn Local optimal helps the global learn Time complexity with V squared E Or V log V with binary heap key From GPS routing to network flow Dijkstra's legacy continues to grow [Verse 3] When the queue is empty then we're complete Every shortest path we did defeat Trace it backwards if you need the route Parent pointers give you absolute From the source to any destination Optimal path with no hesitation Single source to all the rest Dijkstra proved he was the best [Chorus] Relax the edges, update the cost Check every neighbor, nothing gets lost Distance plus weight, compare what you got If it's smaller then update the spot Queue it up, queue it up, mark it done Dijkstra's way till the algorithm's won No negative weights, that's the rule Shortest path finder, ultimate tool [Outro] Graph theory classic from way back when Still solving problems again and again Remember the process, remember the name Dijkstra's algorithm, forever in the game
← Depth-first search (DFS) | Graph Theory Basics for Shortest Paths →