Hands-On Software Engineering with Golang

Leveraging a gossip protocol to run Dijkstra in parallel

Dijkstra's algorithm is fairly straightforward to implement and its runtime can be sped up considerably with the introduction of specialized data structures (for example, min-heap or Fibonacci heap) for selecting the next vertex for each iteration. Let's take a look at how we can leverage the graph processing system that we have built to execute Dijkstra's algorithm in parallel.

To break the sequential nature of the original algorithm, we will swap out the next vertex selection step and replace it with a gossip protocol. Whenever a vertex identifies a better path to it via another vertex, it will broadcast this information to all its neighbors by sending them a PathCostMessage. The ...