A witness path is an alternative route between two neighbors of a node being contracted. If its cost is no greater than the route through that node, the alternative preserves their shortest distance: no shortcut is needed. section 4.3.4
A four-node contraction
Contracting node 1 needs no shortcut between nodes 2 and 4 because their shortest path does not pass through node 1. Contracting node 2, by contrast, changes shortest paths and calls for shortcuts. section 4.3.4
Figure 4.24 Witness path—there is another path from P to w that is shorter, so no shortcut is needed when contracting v.
The diagram contrasts a route through the contracted node with a shorter alternative that makes a shortcut unnecessary. section 4.3.4
This comparison is part of contraction-hierarchy preprocessing. Shortcuts that are needed go into an augmented graph used later for faster queries; a witness path prevents adding one unnecessarily. section 4.3.4
