A multiple edge, also called a parallel edge, is one of several edges connecting the same pair of vertices in a multigraph. Parallel roads, capacities, or social relationships can model distinct connections between identical endpoints. section 3.1
Routing algorithms must preserve edge weights when exploring parallel edges. Choosing the wrong edge can produce a longer route even when the endpoints are identical. section 3.5
A practical normalization strategy for weighted routing graphs is:
- Compare parallel edges connecting the same vertices. section 3.5
- Retain the edge with the lowest weight, such as the shortest road length. section 3.5
- Discard the other parallel edges before applying the adapted shortest-path search. section 3.5
Two routes through the same connection
Suppose vertices 0 and 1 have two parallel edges, and both connect onward to vertex 2. Selecting the upper edge can yield a route length of 7, while selecting the lower, shorter edge yields 3. section 3.5
Figure 3.38 Parallel edges may be problematic because finding the shortest path depends on which parallel edge is selected during graph exploration.
Visualizes why shortest-path results depend on which parallel edge graph exploration selects. section 3.5
