Graphs

A shortest path from vertex \(s\) to vertex \(t\) in an edge-weighted digraph is a directed path from \(s\) to \(t\) with the property that no other path has a lower weight. A shortest-paths tree for a source \(s\) is a subgraph containing \(s\) and all the vertices reachable from \(s\) that forms a directed tree rooted at \(s\) such that every tree path is a shortest path in the digraph....