Learn
Graphs: Conceptual
You're Going to Carry that Weight

We’re building a graph of favorite neighborhood destinations (vertices) and routes (edges), but not all edges are equal. It takes longer to travel between Gym and Museum than it does to travel between Museum and Bakery.

This is a weighted graph, where edges have a number or cost associated with traveling between the vertices. When tallying the cost of a path, we add up the total cost of the edges used.

These costs are essential to algorithms that find the shortest distance between two vertices.

Gym and Library are adjacent, there’s one edge between them, but there’s less total cost to travel from Gym to Bakery to Library (10 vs. 9).

In a weighted graph, the shortest path is not always the least expensive.

Instructions

Why does the route from Gym to Library take so long if it’s adjacent? Well, there’s a vexing swarm of bees in the way!

The critical thing to remember is the shortest path is not always the cheapest.

What are the paths and associated costs with traveling from Museum to Gym?

Folder Icon

Sign up to start coding

Already have an account?