In a directed [[graph]] with weighted edges, the shortest path problem is finding the path from a source to a destination that minimizes the sum of the edge weights traversed. In a **single source shortest path problem**, the source is given and the output is the shortest path to all destinations and the associated costs. In an **all pairs shortest path problem**, find the shortest path for all pairs of vertices and return the cost for each. To store the path, the parent for each destination can be stored instead of the entire path. The full path can be constructed recursively by traversing these parents. Cycles are not a problem for shortest path problems, provided the cycle does not have a negative weight. If a graph has a negative weight cycle, the shortest path is either undefined or could be considered as $-\infty$. Consider that with a negative weight cycle, spinning in that cycle will continually decrease the cost of traversing the path. Even if the negative weight cycle is not taken in the shortest path for a specific destination, it is still more appropriate to think of the cost as undefined. Thus, when negative weight cycles are present in a graph, the solution to any shortest path problem cannot be found. When all weights are the same, the shortest path can be computed simply using breadth-first search.