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.pyOutput
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.