Floyd–Warshall algorithm

A dynamic programming algorithm that computes shortest-path distances between every pair of vertices in a weighted graph. It supports negative edge weights but not negative cycles.

Dynamic programming: An algorithm design method that solves problems by combining solutions to overlapping subproblems. The algorithm stores and reuses distance solutions as the set of allowed intermediate vertices grows.
Dijkstra's algorithm: A greedy algorithm for single-source shortest paths with nonnegative edge weights. Unlike Floyd–Warshall, it solves from one source and cannot handle negative edges safely.
Robert Floyd: An American computer scientist whose work included graph algorithms, programming languages, and program verification. Floyd published a 1962 formulation of the all-pairs shortest-path method.
All-pairs shortest paths: The collection of minimum path costs between every ordered pair of vertices in a graph. This is precisely the output Floyd–Warshall computes.
Weighted graph: A graph whose edges carry numerical values representing costs, lengths, or other quantities. Floyd–Warshall operates on edge weights and compares sums of path weights.
Shortest path problem: The problem of finding a minimum-cost route between vertices in a graph. Floyd–Warshall solves this problem simultaneously for every ordered pair of vertices.
Bellman–Ford algorithm: An algorithm for single-source shortest paths that supports negative edge weights and detects reachable negative cycles. It handles negative weights from one source, while Floyd–Warshall computes all pairs.
Stephen Warshall: An American computer scientist known for an algorithm computing transitive closure of a relation. Warshall’s 1962 recurrence has the same intermediate-vertex structure for reachability.
Transitive reduction: A minimal relation or graph preserving the same reachability as the original. Reachability information from the related Boolean recurrence can support simplification of directed graphs.
Directed graph: A graph whose edges have a specified direction from one vertex to another. The algorithm handles directed edges and can represent an undirected edge with two arcs.

Linked from 4 pages