Car-free in a Car Culture

Taking Transit with Dijkstra’s Algorithm

Feb 7, 2017 · 4 min read

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)

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.

Tech and the City

Hacking it in my hometown of Los Angeles.

Tech and the City

Hacking it in my hometown of Los Angeles. From urban planner to software developer. From Brooklyn to Downtown LA. Getting real nerdy with it.

Written by

Malina Tran

I design and build things for the web through code. Born & based in LA. malinatran.com

Tech and the City

Hacking it in my hometown of Los Angeles. From urban planner to software developer. From Brooklyn to Downtown LA. Getting real nerdy with it.

Phases of the Node JS Event Loop

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app