Graph Algorithms

SSSP — unweighted BFS: algorithm for finding shortest path to vertex (unweighted directed graphs), costs O(m log n) work and O(d log^2 n) span

SSSP — non-negative weights Dijkstra’s: algorithm for finding shortest paths from one vertex to any other vertex with no negative weight cycles. Based on a priority queue implementation popping off “cheapest” visited neighbor and expanding to its corresponding neighbors. Our insertion into a priority queue is O(log m) = O(log n) since we don’t remove duplicate vertices. Each edge is visited once, so the algorithm is O(m log n). The algorithm is not parallelizable inherently, so the span is the same. Thus, APSP with Dijkstra’s is O(nm log n)

SSSP—negative weights and cycles allowed Bellman-Ford: algorithm for finding shortest paths from one source vertex to any other vertex (with negative weights). This is the minimum weight from (n-1) hops, iterating over the number of hops with DP. The shortest path between any 2 vertices u and v is either directly between u and v, or there is some x such that the shortest path travels from u to x to v. dist(v) = min(dist(v), dist(v) + w(x, v)). Then since the path can contain at most n vertices, after n hops we will have the shrotest path for all dist(1 through v). Then this takes O(nm) time because each edge is visited twice in each of the n hop cycles. O(n log n) span.

APSP Floyd-Warshall: best for when you need all paths, supports negative weights but NOT negative cycles. We use an adjacency matrix for quick lookup. This algorithm takes O(n^3) work and O(n) span parallelized. This is again DP where the recurrence is dp(u, v, k) is the shortest path from u to v using only (1…k) as intermediate vertices