There are many “kinds” of shortest paths. Algorithm Constraint Typical Worst Case Topological Sort No directed cycles \(N+M\) \(N+M\)...
A negative cycle is a directed cycle where the sum of the edge weights is negative. A shortest paths tree exists if and only if there...
Given a digraph, we may wish to find the shortest distance between two nodes, or between a node and all other nodes, etc. Each edge has...
Applications When looking at code/library dependencies, one may want to see which code pieces form strongly connected components, and...
Topological Sort A topological sort is a traversal of a digraph with ordering constraints. Let each node have some value/weight. It is a...