Last active
October 5, 2022 05:10
-
-
Save travishen/489e76b9ca774d039b6a8b1c860e1e9a to your computer and use it in GitHub Desktop.
Dijkstra Pseudo Code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node | |
name | |
min_distance | |
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
What is v in distBetween(u, v)? Is v the child of u?