Dijkstra's algorithm

I was just as guilty as many programmers when you ask them what Dijkstra’s algorithm is: “oh it’s BFS with a priority queue…” This made me think one could just drop in a PQueue where one had been using a Queue and you’d be all set. Well, sorta.

Ironically, the original algorithm didn’t use a priority queue at all! But subsequent innovation added it, and though I won’t be using a Fibonacci Heap underneath for the truly speediest implementation, I did implement it with pqueue.

Having finally taken a crack at implementing the algorithm, I’d distinguish it from BFS not by the priority queue per se but by the emphasis on edge weights. The importance of the priority queue is a consequence of wanting to find the smallest weight efficiently. Dijkstra’s algorithm solves BFS as a special case: the case where a weighted graph’s edges are all of the same weight.

This is where I’d point out the difference first: how we write our Node class. With BFS, our nodes don’t need to store weights between edges; nodes only need to store an adjacency list of other Nodes (pointers/references to nodes). Optionally, you can store distance (from root) and a reference to the parent node in the Node, but it’s fine to just track those locally to the BFS function itself, too. (That’s how you’ll see it in most psuedocode.)

1
2
3
4
5
6
7
8
9
10
11
class Node
  attr_reader :value, :adj_list
  attr_accessor :distance, :parent

  def initialize(value)
    @value = value
    @parent = nil
    @distance = Float::INFINITY
    @adj_list = []
  end
end

Making a graph is then a matter of creating your nodes (vertices) and linking them together (populating their adjacency lists).

1
2
3
4
5
6
7
8
9
10
11
one = Node.new(1)
two = Node.new(2)
three = Node.new(3)
four = Node.new(4)
five = Node.new(5)

one.adj_list << two << three
two.adj_list << one
three.adj_list << one << four
four.adj_list << three << five
five.adj_list << four

We need to represent our graph with weights for Dijkstra’s algorithm, because duh, shortest path makes no sense if all the paths are the same.

I decided to do this just by adding edge_list, which is a Hash:

1
2
3
4
5
6
7
class WeightedNode < Node
  attr_accessor :edge_list
  def initialize(value)
    @edge_list = {}
    super
  end
end

Then building the graph is pretty similar to the previous one, but every pair of connected nodes (so, every edge) has a value:

1
2
3
4
5
6
7
8
9
10
11
wone = WeightedNode.new(1)
wtwo = WeightedNode.new(2)
wthree = WeightedNode.new(3)
wfour = WeightedNode.new(4)

wone.edge_list[wtwo] = 4
wtwo.edge_list[wone] = 4
wtwo.edge_list[wthree] = 2
wthree.edge_list[wtwo] = 2
wfour.edge_list[wone] = 1
wone.edge_list[wfour] = 1

Now we have the structure we need (aside from the priority queue implementation¹ which I used this lib for) to calculate the shortest distance to any and every² node:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  require 'pqueue'
  def dijkstra
    nodes.first.distance = 0
    pq = PQueue.new(nodes) { |a, b| a.distance < b.distance }

    until pq.empty?
      (current = pq.pop).edge_list.keys.each do |n|
        alt = current.distance + current.edge_list[n]
        if alt < n.distance
          n.distance = alt
          n.parent = current
        end
      end
    end

    nodes.map(&:value).zip(nodes.map(&:distance))
  end
end

This outputs: [[1, 0], [2, 4], [3, 6], [4, 1]]. (The node value, and the minimum distance to that node.)

If I add a new path to the graph that allows us to reach, say, node 3 faster like so:

1
2
wthree.edge_list[wfour] = 3
wfour.edge_list[wthree] = 3

Then my output the next time becomes: [[1, 0], [2, 4], [3, 4], [4, 1]].

If we specifically want to target the search so we return a path from source to target we just need to do a little bit more work: we need to trace the paths as they are happening, and we need to filter the output for just the source-target path we want. We can do both steps in one if we only track the paths we’re targeting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
  def shortest_path(source, target)
    source.distance = 0
    pq = PQueue.new(nodes) { |a, b| a.distance < b.distance }
    path = []

    until pq.empty?
      (current = pq.pop).edge_list.keys.each do |n|
        if n == target
          u = n
          until u.parent.nil?
            path << u.to_s unless path.include? u.to_s
            u = u.parent
          end
        end

        alt = current.distance + current.edge_list[n]
        if alt < n.distance
          n.distance = alt
          n.parent = current
        end
      end
    end

    path
  end

Now this expectation will pass: expect(graph.shortest_path(wone, wthree)).to eq([[3, 4], [4, 1]]). (Each entry is the node value, then the distance.) In other words, the shortest path to three is via four.

If we look at BFS, we can see how it could be rewritten to just use all our machinery for Dijkstra’s, but with no-ops wherever we were checking weight (edge length):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  def breadth_traversal
    nodes.first.distance = 0
    # we dont need to define <=>
    q = [nodes.first]

    until q.empty?
      # we only need adj_list, not edge_list
      (current = q.shift).adj_list.each do |n|
        # i am skipping the initial node
        next unless n.distance == Float::INFINITY
        # we dont need to define a candidate alt value
        n.distance = current.distance + 1
        n.parent = current
        # incidentally, i only added root node so
        # i have to add n to the queue manually
        q.unshift(n)
      end
    end

    self
  end

So it’s not so much that we can drop a priority queue into BFS and get what we need, but the opposite: we can ignore the fact we’re using a priority queue and get BFS if our nodes have equal weights. Anyway, if you’re curious to play around with my code it’s available on github.