In graph theory, the shortest path problem is the problem of finding a path between two vertices/nodes in a graph such that the sum of the weights of its constituent edges is minimized

Variants of Shortest Path(s) Problem

• single-source shortest paths - given vertex 𝑣 find the shortest path TO every other node
• single-destination shortest paths - given vertex 𝑣 find the shortest path FROM every other node
• single-pair shortest path - given 2 vertices 𝑢 and 𝑣, find the shortest path between them
• all-pairs shortest paths - find the shortest path between all possible pairs of vertices