Corrected Dijkstra's algorithm pseudocode for CS 261 assignment 4

dijkstra.md

Here's complete corrected pseudocode for Dijkstra's algorithm:

for every node N:
  cost[N] = infinity
  prev[N] = undefined

Q = new priority queue
insert N_start into Q with priority 0

while Q is not empty:
  c = Q.first_priority()  // c is the total cost of the path to N
  {N, N_prev} = Q.remove_first()  // N_prev is the previous node on the path to N
  if c < cost[N]:
    cost[N] = c
    prev[N] = N_prev
    for each neighbor N_i of N:  // A neighbor is a node connected to N by an edge
      c_i = cost of edge from N to N_i
      insert {N_i, N} into Q with priority c + c_i  // N is the previous node on the path to N_i