Skip to content

Instantly share code, notes, and snippets.

@quantra-go-algo
Created August 24, 2021 11:02
Show Gist options
  • Save quantra-go-algo/27718fa7db7e02cbb3dbc6b5dba2c537 to your computer and use it in GitHub Desktop.
Save quantra-go-algo/27718fa7db7e02cbb3dbc6b5dba2c537 to your computer and use it in GitHub Desktop.
Pseudo code of Dijkstra algorithm
function Dijkstra(L[1..n, 1..n]): matrix [2..n]
matrix D[2..n]
{initialization}
C <- {2, 3, …, n} {S = N \ C exists only implicitly}
for i ← 2 to n do D[i] ← L[1, i]
{greedy loop}
repeat n - 2 times
v ← some element of C that minimizes D[v]
C ← C \ {v} {and implicitly S ← S U {v}}
for each w ∈ C do
D[w] ← min(D[w], D[v] + L[v, w])
Return D
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment