WeightedTraversal

Abstract base class for weighted graph traversals using a tuple (E, V) frontier.

Encapsulates the shared structure of Dijkstra and Prim: both use an IndexedPrioQueue[(E, V)] frontier, CostUpdate with decreaseKey, and mutable pred/bestCost maps owned exclusively by CostUpdate.

The context bound is E: {Zero, Ordering} — both algorithms need a seed cost (Zero.identity) and a cost ordering (Ordering). Only Dijkstra additionally needs Monoid.combine for path cost accumulation; Prim never accumulates costs and so extends this class directly with E: {Zero, Ordering}. DijkstraTraversal extends this with the additional Monoid bound.

Concrete subclasses differ in exactly three ways:

• edgeCost — how the frontier cost is computed from an edge: cumulative (Monoid.combine) for Dijkstra; edge weight only for Prim.
• destination — how the destination vertex is extracted from an edge: always e.black for directed; e.other(v) for undirected.
• filterEdge — which edges are admitted and what concrete R type they have: only AttributedDirectedEdge for Dijkstra; all edges for Prim.

NOTE on lazy evaluation: ev._1 and ev._2 must be extracted via strict val with explicit type ascriptions inside Neighbours. Using tuple pattern matching val (accCost, v) = ev can generate a lazy binding that captures incorrectly when the resulting Iterator is consumed lazily, causing edgeCost to receive zero instead of the actual accumulated cost (a Heisenbug).