Graph Shortest Path

Problem: Given a weighted or unweighted graph, find the shortest path between two given nodes.

Constraints: Graph can be represented as an adjacency list; may contain up to 10^4 nodes and edges.

Example: Graph: A-B (1), B-C (2), A-C (5). Shortest path from A to C is A->B->C with cost 3 (vs direct A->C at cost 5).

Approach: For unweighted graphs, use BFS (O(V+E)). For weighted graphs with non-negative weights, use Dijkstra's algorithm with a min-priority-queue (O((V+E) log V)). If negative weights are possible, use Bellman-Ford (O(V*E)). Reconstruct the path by tracking predecessor pointers during traversal.