Graphs Algorithms

Arranges the vertices of a directed acyclic graph (DAG) in a line so that every edge points only forward. Kahn's algorithm keeps nodes with indegree 0 in a queue and emits them in turn, forming the basis of task scheduling, dependency resolution, and build ordering.

Finds the shortest distances from a source node in a weighted graph with no negative edges. Its greedy strategy uses a priority queue to fix the closest node each round and relax its neighbors, making it the standard for navigation and network routing.

A shortest-path algorithm that works even with negative edges. Relaxing every edge V−1 times converges to the shortest distances, and one extra relaxation detects a negative cycle. Slower than Dijkstra, but more general.

Sorts all edges by ascending weight, then adopts only the edges that don't form a cycle to build a minimum spanning tree (MST). Cycle checks run in O(α) with union-find.

Starts from one node and grows a minimum spanning tree by adding the cheapest edge connected to the tree, one at a time. It manages candidate edges with a priority queue and grows in a different order than Kruskal, but reaches the same MST.