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.

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`

?