A* Search
Goal-directed shortest path that orders Dijkstra's pick by distance-so-far plus a heuristic estimate of the remaining distance to a goal, shown with a Manhattan heuristic computed once from per-vertex grid coordinates.
Read algorithmEDGE Algorithms
This site presents graph algorithms written in EDGE (Extended General Einsums for Graph Algorithms), with structured sections, working examples, and full LaTeX support via MathJax.
The EDGE language as described here: The EDGE Language: Extended General Einsums for Graph Algorithms.
Bellman-Ford (Single-Source Shortest Paths)
Single-source shortest paths that relaxes every edge each round and re-relaxes vertices whenever a strictly shorter path appears, expressed as a four-step extended Einsum iterated to a fixed point.
Read algorithmBreadth-First Search (Depth-Tracking)
Level-synchronous BFS that records the hop-distance of every vertex from a source set, expressed as an iterated extended Einsum over a graph tensor.
Read algorithmBubble Sort
In-place comparison sort that repeatedly bubbles the largest unsorted element rightward by a sweep of adjacent compare-exchanges, expressed as a nested cascade over a pass rank and a step rank where each step keeps the min on the left and the max on the right of an adjacent pair.
Read algorithmConnected Components (Label Propagation)
Connected components by max-label propagation, where every vertex repeatedly adopts the largest label among itself and its neighbours until labels stop changing, expressed as a single iterated extended Einsum over a symmetric, reflexive graph tensor.
Read algorithmDepth-First Search (Stamped-Stack)
Sequential depth-first search that carries an explicit stack as a tensor of order stamps, popping the most recently pushed vertex each round, expressed as an iterated extended Einsum over a graph tensor.
Read algorithmDijkstra (Single-Source Shortest Paths)
Single-source shortest paths that settles one vertex per round — always the closest unsettled vertex — and relaxes only its out-edges, expressed as Bellman-Ford's relaxation body wrapped in a priority queue. Requires non-negative edge weights.
Read algorithmFloyd-Warshall (All-Pairs Shortest Paths)
All-pairs shortest paths as a per-pivot min-plus closure, where iteration $i$ admits paths that route through pivot vertex $i$ and the distance tensor is tightened against the through-pivot candidate, iterated once over every vertex.
Read algorithmMaximum Flow (Push-Relabel)
Maximum s-t flow by the bulk-synchronous push-relabel method, which seeds a saturating preflow from the source and then repeatedly pushes excess down admissible residual edges and relabels stuck vertices, expressed as one long extended Einsum iterated until no internal vertex holds excess.
Read algorithmPost-Order Depth-First Search
Depth-first search that records each vertex when its entire subtree is finished rather than when it is first discovered, expressed as a stamped-stack Einsum that touches every vertex twice and writes a finish time on the way out.
Read algorithmShortest Path Faster Algorithm (SPFA)
Single-source shortest paths that relaxes only vertices whose distance recently improved, by wrapping Bellman-Ford's relaxation body in a work queue — sitting exactly between Bellman-Ford (relax everything) and Dijkstra (relax the closest), and tolerating negative edge weights.
Read algorithmSparse Matrix-Vector Multiply (SpMV)
The foundational sparse-linear-algebra primitive, expressed as a single extended Einsum whose intersection merge skips absent matrix entries and whose reduction sums each output row, with a semiring dial that turns the same expression into BFS-advance and shortest-path relaxation.
Read algorithmTriangle Counting
Counts the triangles in an undirected graph as a single masked Einsum that multiplies two adjacency hops and keeps only the products that land on an existing edge, then reduces the masked counts to a total.
Read algorithmWidest Path (Maximum Bottleneck Path)
Single-source maximum-bottleneck paths that widen a wavefront of bottleneck capacities each round and keep the best capacity seen so far, expressed as the max-min mirror of min-plus Bellman-Ford iterated to a fixed point.
Read algorithm