Dijkstra's algorithm

Dijkstra’s algorithm is a pathfinding algorithm that lets us find the “ideal” path in a Weighted graph, taking the weights of the vertices into consideration.

A good analogy for understanding Dijkstra’s algorithm is finding the fastest path between node A and node B, as opposed to simply finding the shortest path (fewest connections) between node A and node B.^[1] Imagine that each edge between node A and node B has a speed limit. If this is the case, then the shortest path may not be the fastest. The speed limits are weights which Dijkstra’s algorithm can take into consideration when finding the ideal path between nodes A and B. The “speed limit” concept in this example is often referred to as “cost” in the context of pathfinding algorithms.

Steps

1. Find the “cheapest” node.
2. Check whether there’s a “cheaper” path to the neighbors of this node. If so, update their costs.
3. Repeat steps 1 and 2 for every node in the graph.
4. Calculate the final “cheapest” path.

In practice

In practice, this looks like creating an “adjacency list” where we keep track of each node and update its cost as we execute the algorithm. An adjacency list is just a list containing the queued nodes in the graph (see Breadth-first search) along with their costs. Until the cost of a given node is known, it is considered to be infinite. We also keep track of each node’s parent in the list.

Consider a weighted graph:

graph = {}
graph["chicago"] = [
  ("detroit", 1),
  ("st. louis", 4),
  ("minneapolis", 2)
]
graph["detroit"] = [
  ("chicago", 2),
  ("toronto", 1)
]
graph["minneapolis"] = [
  ("st. louis", 3),
  ("seattle", 6),
  ("boise", 5)
]
graph["st. louis"] = [
  ("chicago, 4),
  ("nashville", 4),
  ("tulsa", 2)
]
graph["nashville"] = [
  ("st. louis", 4),
  ("tulsa", 6),
  ("charlotte", 2)
]

An adjacency list for this graph might look like this:

In this list, Detroit, St. Louis, and Minneapolis are immediate neighbors of Chicago, so their costs are “known”. Once we reach the next queued nodes, we update their costs and parents in the table.

So, let’s follow the steps.

1. Find the “cheapest” node.

In this case, Detroit is the cheapest connection to Chicago. Is there a cheaper way to get to Detroit? No, since we’re only dealing with one degree of separation and Detroit is the cheapest node in our system so far.

2. Figure out how cheap the first node’s neighbors are (the cost)

The only neighbor of Detroit we haven’t yet visited is Toronto, which has a cost of 1 from Detroit. So, we update our adjacency list accordingly:

3. Repeat steps 1 and 2

Minneapolis is the next cheapest node from Chicago, so we update the adjacency list with neighbors of Minneapolis:

Note that St. Louis is accessible from Minneapolis more cheaply from Minneapolis than from Chicago (for our purposes at least), so we’ve updated the parent and cost of St. Louis accordingly.

After repeating steps 1 and 2 for each node, we get an adjacency list that looks like this:

Note that each node in the list now corresponds to its “cheapest” parent.

4. Calculate the final “cheapest” path

Now, we can “work backwards” through the adjacency list to find our final path.

Consider a path between Chicago and Tulsa. Tulsa’s cheapest parent is St. Louis, whose cheapest parent is Minneapolis, whose cheapest parent is Chicago. Therefore, the cheapest path from Chicago to Tulsa is:

Chicago -> Minneapolis -> St. Louis -> Tulsa

Implementation

Dijkstra’s algorithm can be implemented using three Hash tables: graph, costs, and parents.

The graph table is our weighted graph:

graph = {}
graph["chicago"] = [
  ("detroit", 1),
  ("st. louis", 4),
  ("minneapolis", 2)
]
graph["detroit"] = [
  ("chicago", 2),
  ("toronto", 1)
]

...

The costs table contains our costs for each node:

costs = {}
costs["detroit"] = 1
costs["st. louis"] = 4
costs["minneapolis"] = 2
costs["toronto"] = float("inf")  # infinity in Python

...

The parents table contains our lowest-cost parent for each node:

parents = {}
parents["detroit"] = "chicago"
parents["st. louis"] = "chicago"
parents["minneapolis"] = "chicago"
parents["toronto"] = None

...

We also need a list to keep track of the nodes we’ve already visited:

visited = []

Here are the steps our code must execute:

while we have nodes to process...
grab the node closest to the start
update costs for its neighbors
if any of the neighbors' costs were updated, update parents
mark this node as visited

The Python code looks like this:

node = find_lowest_cost_node(costs)

while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  
  for n in neighbors:
    new_cost = cost + neighbors[n]
    
    if costs[n] > new_cost:
      costs[n] = new_cost
      parents[n] = node
  
  visited.append(node)
  node = find_lowest_cost_node(costs)

Breaking cases

• Negative-weight edges
  • negative-weight edges are edges that have negative costs… in other words, gain
  • edges with negative weight break Dijkstra’s algorithm because the algorithm doesn’t attempt to calculate the cheapest combination of connections between each node, but simply the lowest cost direct-connections for each node. This could result in a case where a higher-cost neighbor is preferable because it grants access to a negative-weight connection that cancels the higher cost of the first connection, which Dijkstra’s algorithm doesn’t attempt to compensate for.
• Cycles
  • cycles are 2-way connections between two nodes, meaning that the nodes are both connected to each other (not just one to another). Indeed, all connections in undirected graphs are cycles. This is relevant to Dijkstra’s algorithm because each edge in a cycle has a weight, meaning that cycles can introduce infinite loops of cost to our algorithm.
  • “Dijkstra’s algorithm only works on graphs with no cycles, or on graphs with a positive weight cycle.”^[1:1]