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
?