Hands-On Software Engineering with Golang

The sequential Dijkstra algorithm

Before we adapt Dijkstra's algorithm so that it works with our graph processing system, we need to have a clear idea of how the original algorithm works. The following snippet outlines an implementation of the sequential version of Dijkstra's algorithm in pseudocode form:

function Dikstra(Graph):
  for each vertex v in Graph:
      min_cost_via[v] = infinity
      prev[v] = nil
  min_cost_via[src] = 0
  
  Q = set of all vertices in graph
  while Q is not empty:
    u = entry from Q with smallest min_cost_via[]
    remove u from Q

    for each neighbor v from u:
      cost_via_u = min_cost_via[u] + cost(u, v)
      if cost_via_u < min_cost_via[v]:
        min_cost_via[v] = cost_via_u
        prev[v] = u

The preceding implementation maintains two arrays, each one having ...