An edge weight is a numerical value attached to a graph edge. It represents a cost, distance, travel time, or another domain-specific measure. For a path, add the weights of its edges; the minimum-distance path is the one with the smallest total. section 14.4.1
This changes how shortest-path algorithms choose what to explore. Breadth-first search counts edges, so a path with fewer hops wins. Dijkstra’s algorithm instead orders discovered vertices by accumulated edge weight, using a priority queue rather than a plain queue. section 14.4.1
A longer route can be cheaper
Suppose one route from v1 to v2 uses v1→v3→v2 with total weight 8. Another uses v1→v3→v5→v2 with three edges but total weight 5. The second route is longer by hop count yet preferable by edge weight, so Dijkstra’s algorithm updates v2’s priority from 8 to 5. section 14.4.3
Use edge weights to model different measurable objectives:
- Use meters to represent physical distance between intersections. section 14.4.1
- Use travel time when traffic, weather, or closures change the cost of traversing a road. section 14.5.2
- Keep heuristic estimates comparable with edge weights by using compatible units or scaling. section 14.5.2
Figure 14.17 Overlaying a directed weighted graph over the map in figure 14.16. Edges’ weights are the distances (in meters) between the intersections modeled by the edge’s vertices.
View a directed road graph whose edge weights are distances in meters between modeled intersections. section 14.4.1
