Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Dijkstra Pseudo Code
class Node
Node predecessor
function Dijkstra(Graph, source):
distance[source] = 0 // distance from source is 0 because it's the starting point
create queue Q
for n in Graph
distance[n] = infinity // initial phase: other nodes distances are infinity(as guess)
// because we don't know yet
predecessor[n] = undefined // node's previous node in the shortest path is un-known
add n to Q
while Q not empty
u = node in Q with min distance // this is why to use heaps
remove u from Q // heap will reconstruct after remove
for each neighbor n of u // find shorted path and update distance, predecessor
tempDist = distance[u] + distBetween(u, v)
if tempDist < distance[v]
distance[v] = tempDist
predecessor[v] = u
return distance[]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment