Paul's Python CoursePPC

Weighted graphs

Not met yet

A weighted graph puts a number on each connection: minutes on a road, pence on a fare, kilos on a crane lift. In Python, give each place a dictionary of its neighbours instead of a list, so MINUTES["gym"]["market"] is the minutes from the gym to the market. A route's length is the sum of its roads' weights, so the route with the fewest roads isn't always the shortest. zip(route, route[1:]) pairs each place with the next one along.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks the length of a route in a weighted graph is how many roads it has, not the sum of the numbers on them.
  • Thinks the route with the fewest roads is always the quickest, whatever the roads weigh.
  • Thinks the numbers in a weighted graph belong to the places rather than to the roads between them.
  • Thinks zip(route, route[1:]) pairs the last item with the first, as if the list went round in a circle.

Where it comes up