Single-Pair Shortest Path (SPSP)

overview

Summary

Single-pair shortest path finds the minimum-cost route between one source node and one target node in a graph. It differs from single-source and all-pairs problems by optimizing effort for just one pair. The choice of algorithm depends on edge weights and graph properties: BFS for unweighted, Dijkstra for nonnegative weights, Bellman-Ford for negative edges, and A* or bidirectional search to speed up single-pair queries. Key implementation details include early stopping when the target is finalized and tracking parent pointers to reconstruct the path.