Car-free in a Car Culture

Taking Transit with Dijkstra’s Algorithm

Before getting started, here are some terms I’ll be using:

• Graph: models a set of connections (e.g. Person A → Person B; Person C → Person B, etc.)
• Neighbor: a direct connection (e.g. A is a neighbor of B, and vice versa)
• Edge: the relationship between two neighbors (e.g. that arrow → which may or may not have a weight or value associated with it)
• Parent: the node from the left side of the arrow (e.g. If my diagram shows Person A → Person B, then A is considered the parent of B)

The inspiration for my example.

As a transit rider, I have to make all sorts of decisions about how to get from point A (let’s use the Central Library in Downtown LA) to point B (Annenberg Space for Photography in Century City). Through a breadth-first search, I can ask myself the following questions:

• Is there a path from my origin to destination?
• What is the shortest path from my origin to destination?

Ideally, I’d like the least number of transfers and the fewest number of buses and trains. However, the limitation of a breadth-first search is that it will provide the shortest path (based on number of segments), but does not account for the duration of those bus and train trips. What if one bus ride is longer than two bus rides? Or a train is longer than walking and riding a train? There are multiple scenarios in which fewer segments could actually take a longer period of time.

Here is a graph demonstrating the trip from Central Library to The Annenberg Space. The bus lines or nodes are indicated in black font; the arrows are the edges; and the yellow number represent the minutes spent for the segment of the trip.

To better understand which path to take, the solution is to use Dijkstra’s algorithm. The algorithm provides more insight to the preferred route based on the fastest path as determined by the weight of an edge. First things first, let’s create hashtables that represent the graph, costs, and parents. I like to think of the graph hashtable as mapping all of the relationships between nodes.

As you can imagine, the hashtable for the first chart would look something like this (hashtables within hashtables).

graph = { “Central Library”=>{“431”=>2, “14”=>0, “910”=>3},
          “431”=>{“3”=>45},
          “3”=>{“Annenberg”=>5},
          “14”=>{“28”=>30},
          “28”=>{“Annenberg”=>30},
          “910”=>{“28”=>45},
          “Annenberg”=>{}}

And we’ll have two more hashes called costs and parents, which will be referenced in the code below.

There are four steps to Dijkstra’s algorithm:

1. Find the cheapest node (line 4; see code for method at the bottom)
   “Cheapest” node refers to the node that will get you there in the least amount of time. We’ll start off with the first segment of the trip. The start is Central Library; the end is The Annenberg Space for Photography. The cheapest node would be the 14 bus, since the cost is 0 minutes. You can’t get any lower than zero (if dealing with negative weight, you’d have to use the Bellman-Ford algorithm).
2. Update the costs of the neighbors of the node (lines 13–16)
   The 28 bus is the only neighbor of 14, and the cost would be 0 + 30 = 30 minutes. Since 30 is not greater than 30, there is nothing to update.
3. Repeat this for every node in the graph (lines 10 & 20)
   After we’ve checked the node and its neighbor, we store the node’s value into an array. Next, we’ll check the next-cheapest node, which is the Commuter Express 431 with a cost of 2 minutes and neighbor of 3 with a cost of 45 minutes. The last node is 910 with a cost of 3 minutes.
4. Calculate the final path. Naturally, this would get more complex if there are more bus lines and more possibilities. By returning the parents hashtable, we’ll see what’s the final path. By tracing backward, we can see that to get to The Annenberg, we’d take the 3 and in order to get the 3, we’d catch the 431 from the Central Library.

{“431”=>”Central Library”, 
 “3”=>”431", 
 “14”=>”Central Library”, 
 “28”=>”14", 
 “910”=>”Central Library”, 
 “Annenberg”=>”3"}

FYI, here’s how we’ll find the lowest/cheapest node. We set the lowest cost to be infinity and the lowest node to be empty. We’ll iterate through the costs hashtable. The bus line represents the key; the duration in minutes, the value. Since we aren’t sure how long it will take to The Annenberg, we set this value to infinity.

costs = {“431”=>2, 
         “14”=>0, 
         “910”=>3, 
         “Annenberg”=>Float::INFINITY, 
         “3”=>45, 
         “28”=>30}

We’re essentially looking through this collection to see which one has the lowest value. Once we’ve processed the node, we’ll include it in our processed array so it won’t be processed again. Our return value is the node, or in this case, the bus line.