Algorithm dossier

  • Category: Shortest path
  • Worst-case complexity: O(n³)
  • Approach: DP
  • Data structure: Graph
  • First formalised: 1960s

Why this snippet is Floyd-Warshall

Why Floyd-Warshall. All-pairs shortest paths via dynamic programming. The triple-nested loop with k *outermost* is the signature — the invariant after iteration k is "d[i][j] is the shortest path using vertices {0..k} as intermediates." Reverse the loop order and the algorithm silently breaks. Trade-off. O(n³) but tight inner loop, no priority queue — beats running Dijkstra n times on dense graphs.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.