Weights on the edges
A weighted graph carries a number on each edge, called its weight: a distance, a cost or a time. Only the number counts. An edge drawn short may carry a large weight.
The network below has five vertices and eight edges. A to B weighs 4, A to C 2, B to C 5, B to D 6, B to E 9, C to D 8, C to E 3 and D to E 7.
Five vertices and eight edges, each carrying its weight.
The table
The weighted adjacency table has a row and a column for each vertex, like the adjacency table. Where an edge joins two vertices, the entry is its weight, in place of the 1. Where no edge joins them, the entry is a dash.
A dash and a 0 mean different things. A 0 would read as an edge that costs nothing to use, so a pair with no edge gets a dash, or a blank, and never a 0. The diagonal holds dashes too, because no vertex has an edge to itself.
The weights in the table. Row A has dashes under A, D and E, because the only edges at A are AB and AC.
Reading an entry
Row B, column D holds 6, so the edge from B to D has weight 6. Row D, column B holds 6 as well: an edge weighs the same from either end, so the table is symmetric across its diagonal, like an adjacency matrix.
Row B holds 4, 5, 6 and 9, one weight for each of the four edges at B, so B has degree 4: the degree is the number of entries in the row that are not dashes. Adding the row gives something else, the total weight of the edges at B: 4 + 5 + 6 + 9 = 24.
Row B, column D holds 6, the weight of the edge from B to D. Its mirror, row D, column B, holds 6 too.
The cost of a route
A route costs the sum of the weights along it. A to B to D costs 4 + 6 = 10. A to C to D costs 2 + 8 = 10 as well, so two routes tie for the cheapest from A to D, while A to C to E to D costs 2 + 3 + 7 = 12.
A route with fewer edges is not always cheaper. From B to E the direct edge weighs 9, but B to C to E costs 5 + 3 = 8. The cheapest route between two vertices is known only once the other routes have been priced.
A to B to D, in gold, costs 4 + 6 = 10.
From B to E, the gold route through C costs 5 + 3 = 8, less than the dashed direct edge at 9.
Weights that depend on the direction
Some weights differ with the direction: a fare that costs more one way, or a road that takes longer uphill. The graph is then directed, and row X, column Y holds the weight from X to Y only, so the table need not be symmetric.
The usual mistakes
Reading the cell beside the one asked for. Run along row B as far as column D, and read 6.
Pricing a route by its dearest edge. A route pays for every edge it uses: A to B to D costs 4 + 6 = 10, not 6.
Subtracting one weight from the other. The two edges of A to B to D are used one after the other, so their weights add.
Writing 0 where no edge exists. A 0 says the pair is joined at no cost.
Taking the direct edge as the cheapest way between its ends. From B to E, the route through C is cheaper.
Freight charges and driving times
In the first application below, a crate pays for every flight it takes, so each route with one stop and with two stops is priced and the cheapest chosen. In the second, a road is on no fastest route when a way round through other towns is quicker, as B to C to E beats the direct edge above.
Worked example: Air-Freight Charges Between Five Cities, and the Cheapest Way to Send a Crate With One Stop or Two
Question An air-freight company charges a fixed price per crate for each direct flight it runs between five cities, A, B, C, D and E. Its table of charges, in dollars, is A–B 40, A–C 25, A–D 55, B–C 20, B–D 30, B–E 45, C–D 25, C–E 70 and D–E 15. Every flight runs both ways at the same price, and there is no direct flight between A and E. A crate sent on a route with stops pays for every flight it takes. (a) What is the cheapest route from A to E with exactly one stop, and what does it cost? (b) What is the cheapest route from A to E with exactly two stops, and how much does it save on the route in (a)?
1.Read the table as a weighted graph: a vertex for each city and an edge for each direct flight, weighted with its charge. A route costs the sum of the weights along it. There is no edge between A and E, so a crate has to stop at least once.
The table is a weighted graph: each charge is the weight of an edge. There is no edge between A and E. 2.With one stop at X, the cost is the charge from A to X plus the charge from X to E. Through B it is 40 + 45 = 85. Through C it is 25 + 70 = 95. Through D it is 55 + 15 = 70.
With one stop at X, a crate pays the charge from A to X plus the charge from X to E. 3.(a) The cheapest route with one stop is A–D–E, costing $70. It starts with the most expensive flight out of A, but the cheap flight from D to E more than makes up for it.
(a) A–D–E costs 55 + 15 = $70, the least of the three. 4.With two stops, the route is A–X–Y–E, where X and Y are two different cities from B, C and D. The six routes cost: A–B–C–E 40 + 20 + 70 = 130, A–B–D–E 40 + 30 + 15 = 85, A–C–B–E 25 + 20 + 45 = 90, A–C–D–E 25 + 25 + 15 = 65, A–D–B–E 55 + 30 + 45 = 130 and A–D–C–E 55 + 25 + 70 = 150.
The six routes with two different stops, each costed along its three flights. 5.(b) The cheapest route with two stops is A–C–D–E, costing $65, which saves 70 − 65 = $5 on the route in (a). The extra stop pays because going from A to D through C costs 25 + 25 = 50, less than the direct flight at $55.
(b) A–C–D–E costs $65, which saves $5 on A–D–E.
Answer: (a) A–D–E, costing $70; (b) A–C–D–E, costing $65, which saves $5
Common mistakes
- Starting with the cheapest flight out of A, A–C at $25, and carrying on from C. The flight from C to E costs $70, so that route totals $95; every stop has to be tried.
- Assuming that a route with more stops always costs more. Going from A to D through C costs $50, less than the direct flight at $55, so a route with two stops can beat the best route with one.
Worked example: Driving Times on the Roads Between Five Towns, and Which Road No Fastest Trip Uses
Question Seven roads join five towns, A, B, C, D and E, and a table gives the driving time on each road, in minutes: A–B 12, A–C 20, B–C 6, B–D 12, C–D 7, C–E 15 and D–E 10. Every road can be driven both ways in the same time, and there are no other roads. (a) One of these roads is on no fastest route between any two of the towns. Which road is it? (b) What is the fastest driving time from A to E, and which route gives it?
1.Read the table as a weighted graph, with a vertex for each town and each road weighted with its time. A road is on no fastest route when some other route between its two ends is quicker: any trip that uses the road could go round that way instead and arrive sooner.
Each town is a vertex and each road an edge, weighted with its driving time. 2.Test the road A–C, which takes 20 minutes. The route A–B–C takes 12 + 6 = 18 minutes, which is quicker, so A–C is on no fastest route.
The route A–B–C, 12 + 6 = 18 minutes, beats the road A–C at 20. 3.Test the other roads the same way. B–D takes 12 against 6 + 7 = 13 for B–C–D, and C–E takes 15 against 7 + 10 = 17 for C–D–E. A–B, B–C, C–D and D–E are each quicker than every way round. So each of these six roads is the fastest route between its own two ends.
Every other road is quicker than each way round between its own two ends. 4.(a) The road between A and C is the one on no fastest route: a trip between A and C is quicker through B.
(a) The road A–C: any trip on it goes quicker through B. 5.For the fastest time from A to E, build up the fastest time to each town from A. B takes 12. C takes 12 + 6 = 18 through B, quicker than 20 direct. D takes 12 + 12 = 24 through B, or 18 + 7 = 25 through C, so 24. E takes 18 + 15 = 33 through C, or 24 + 10 = 34 through D, so 33.
The fastest times from A, built up town by town: 12, 18, 24 and 33. 6.(b) The fastest time from A to E is 33 minutes, on the route A–B–C–E. Check against the other routes: A–B–D–E takes 34, A–B–C–D–E takes 35, A–C–E takes 35 and A–C–D–E takes 37 minutes.
(b) 33 minutes, on the route A–B–C–E.
Answer: (a) The road between A and C; (b) 33 minutes, on the route A–B–C–E
Common mistakes
- Keeping A–C because it is the only road straight from A to C. A direct road is not always the quickest: A–B–C takes 18 minutes against its 20.
- Taking the route with the fewest roads, A–C–E, as the fastest. It takes 35 minutes, 2 more than A–B–C–E.