Shortest Path in a Graph

Problem Given a graph, find the shortest distance from a source node to a target node (or from a source to all other nodes), and reconstruct the actual sequence of nodes on that path — not just its cost. Choose the right algorithm based on whether the graph is weighted and whether weights can be negative.

Input / Output

• Input: a graph as an adjacency list, a source node, and (optionally) a target node.
• Output: the shortest distance — edge count for unweighted graphs, total weight for weighted ones — plus the node sequence realising it, or the full distance array from the source. Unreachable nodes report infinity / no-path.

Constraints

• Up to ~10^4 nodes and edges: sized so an O(V+E) or O(E log V) solution passes; O(V^3) Floyd-Warshall is only viable for small V.
• Weights may be absent (unweighted), non-negative, or negative depending on the variant.
• Graph may be directed or undirected, and may be disconnected.

Example

• Unweighted graph, distance from A to B as number of edges: A-B, B-C, A-C → distance A to C is 1 edge.
• Tricky case: with weights A-B (1), B-C (2), A-C (5), the fewest-edges path (A→C, cost 5) is not the cheapest path (A→B→C, cost 3) — edge count and weight are different objectives.
• Ties in cost mean several valid paths exist — clarify whether any one is acceptable.