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 Node
s
(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^{1} which I used this lib for) to calculate the shortest distance to any and every^{2} 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 sourcetarget 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 noops 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.

I found a great guide for implementing a priority queue from scratch, which I may try out later. ↩

When I first read through the algorithm, I noticed this Lemma:
Lemma 1: Optimal Substructure
The subpath of any shortest path is itself a shortest path.
I was a bit confused at first, because I wasn’t thinking about how the algorithm is calculating all the possible shortest paths. ↩