--- title: "Floyd-Warshall Algorithm | Combinatorics" description: "Floyd-Warshall Algorithm finds shortest paths between every pair of vertices in a weighted graph using dynamic programming in Combinatorics." canonical: "https://fiveable.me/combinatorics/key-terms/floyd-warshall-algorithm" type: "key-term" subject: "Combinatorics" unit: "Unit 14" --- # Floyd-Warshall Algorithm | Combinatorics ## Definition The Floyd-Warshall Algorithm is a dynamic programming method for finding shortest paths between every pair of vertices in a weighted graph. In Combinatorics, it shows up in graph theory and shortest-path problems. ## What It Is The Floyd-Warshall Algorithm is an all-pairs shortest path algorithm in Combinatorics. Instead of picking one source vertex and spreading outward, it checks every pair of vertices and keeps improving their shortest distance as it allows more possible intermediate vertices. The setup is a distance matrix. At the start, each entry is either the direct edge weight from one vertex to another or infinity if no edge exists. The diagonal usually starts at 0 because the distance from a vertex to itself is zero. Then the algorithm runs through the vertices one by one as possible intermediates. For each ordered pair (i, j), it asks a simple question: is going from i to j through the current intermediate vertex k shorter than the best route we already know? If yes, the matrix entry gets updated. That is the dynamic programming part. Each round builds on the results from earlier rounds, so the algorithm does not recompute everything from scratch. By the end, the matrix stores the shortest distance between every pair of vertices, not just one path from one starting point. A compact example helps. Suppose A to C is 10 directly, but A to B is 3 and B to C is 4. When B is allowed as an intermediate vertex, the algorithm replaces 10 with 7 because A to B to C is shorter. It repeats this kind of check for every pair and every possible middle vertex. The algorithm also works with negative edge weights, which is useful in some combinatorics and graph theory problems, but it cannot handle negative weight cycles. If a cycle keeps making a path cheaper forever, the idea of a shortest path breaks down. One common signal is a negative number appearing on the diagonal of the final matrix. ## Why It Matters Floyd-Warshall matters in Combinatorics because it turns a graph problem into a clean matrix update process. That makes it a nice example of how graph theory and dynamic programming work together, especially when the goal is not just one path but every pair of distances. It shows up whenever a problem asks for the cheapest, shortest, or least-cost route between all vertices in a network. That could be a transportation graph, a communication network, or a weighted relationship graph in a class problem set. If the graph is dense, the algorithm is often more natural than running a single-source method over and over. It also teaches a useful way of thinking about optimization: improve a solution by deciding which intermediates are allowed. That pattern appears in other dynamic programming ideas too, so Floyd-Warshall is good practice for reading recurrence-style logic in graph form. Another reason it matters is that it gives a built-in check for negative cycles. In a graph theory exercise, that can tell you whether the shortest-path question even makes sense. If the diagonal of the final matrix goes negative, you know the graph has a problem that changes the whole interpretation of the answer. ## Connections ### Shortest Path Problem Floyd-Warshall is one way to solve the shortest path problem, but it solves the all-pairs version instead of just one start point. That means you get the shortest distance between every ordered pair of vertices. If a question asks for the best route from one node to all others, that is a different setup, even though the same graph ideas are involved. ### Dynamic Programming The algorithm is a classic dynamic programming example because it builds a better answer from smaller allowed subproblems. Each step asks whether adding one more intermediate vertex improves the current distances. If your class is talking about recurrences or staged optimization, Floyd-Warshall is a graph-based version of that idea. ### Graph You need a weighted graph before Floyd-Warshall has anything to work on. The vertices become the rows and columns of the distance matrix, and the edges become the initial known distances. Understanding the graph structure is what lets you see why the matrix updates make sense. ### [directed graph](/combinatorics/key-terms/directed-graph) Floyd-Warshall works especially cleanly on directed graphs because the distance from i to j can be different from the distance from j to i. That direction matters when you fill the matrix and when you check updates. If the graph is directed, you cannot assume symmetry in the answer. ## On the AP Exam A problem set question might give you a weighted graph and ask you to fill in the distance matrix after one or more Floyd-Warshall passes. Your job is to compare the current entry d(i, j) with d(i, k) + d(k, j) for each intermediate vertex k and update only when the new route is shorter. If the graph includes a negative edge, you should still track the matrix carefully and check whether any diagonal entry becomes negative at the end. If it does, that points to a negative cycle, which means shortest paths are not well-defined. You may also be asked to interpret the final matrix, identify the shortest distance between two specific vertices, or explain why this algorithm is better suited to dense graphs than repeated single-source searches. ## Floyd-Warshall Algorithm vs Shortest Path Problem The shortest path problem is the task, while Floyd-Warshall is one algorithm for solving a version of that task. The confusing part is that people sometimes use the term as if it names the whole problem. In Combinatorics, Floyd-Warshall specifically targets the all-pairs shortest path problem. ## Key Takeaways - Floyd-Warshall finds the shortest path between every pair of vertices in a weighted graph. - It uses a distance matrix and improves entries by testing whether an intermediate vertex creates a shorter route. - The algorithm is a dynamic programming method, so each stage builds on earlier distance information. - It can handle negative edge weights, but negative cycles make the shortest-path answer invalid. - A negative value on the diagonal of the finished matrix is a warning sign for a negative cycle. ## FAQs ### What is Floyd-Warshall Algorithm in Combinatorics? It is a dynamic programming algorithm for finding the shortest distances between all pairs of vertices in a weighted graph. In combinatorics, it belongs to graph theory and shortest-path algorithms. You usually represent the graph as a distance matrix and update it by checking possible intermediate vertices. ### How does Floyd-Warshall Algorithm work? Start with a matrix of direct edge weights, using infinity where no edge exists. Then let each vertex act as a possible middle point and see whether going through that vertex shortens any path. If d(i, k) + d(k, j) is smaller than d(i, j), you replace the old value. ### Can Floyd-Warshall Algorithm handle negative weights? Yes, it can handle negative edge weights as long as there is no negative weight cycle. That is one reason it stands out from some other shortest-path methods. If a negative cycle exists, the notion of a shortest path breaks because you can keep looping to lower the total cost. ### What is the difference between Floyd-Warshall and a single-source shortest path algorithm? Floyd-Warshall solves the all-pairs version, so it gives shortest distances between every pair of vertices. A single-source algorithm starts from one vertex and finds the best routes from that source to the rest of the graph. If you need a full matrix of distances, Floyd-Warshall is the fit. ## Related Study Guides - [14.3 Shortest path algorithms](/combinatorics/unit-14/shortest-path-algorithms/study-guide/FvDVxAKuEiuBldQG) ## About This Document Canonical Fiveable pages are available as Markdown at the same path plus `.md`. - [llms.txt](https://fiveable.me/llms.txt): index of Fiveable's sections and URL patterns - [llms-full.txt](https://fiveable.me/llms-full.txt): complete subject and unit listing - [MCP server](https://fiveable.me/mcp): call Fiveable as tools instead of fetching pages (`https://fiveable.me/api/mcp`) - [MCP server for AP teachers](https://fiveable.me/mcp/teachers): a teacher's classes, assignments and AP-rubric grading (`https://fiveable.me/api/mcp/teacher`) ## Structured Data ```json {"@context":"https://schema.org","@graph":[{"@type":"LearningResource","@id":"https://fiveable.me/combinatorics/key-terms/floyd-warshall-algorithm#resource","name":"Floyd-Warshall Algorithm | Combinatorics","url":"https://fiveable.me/combinatorics/key-terms/floyd-warshall-algorithm","learningResourceType":"Concept explainer","educationalLevel":"AP® / High School","about":{"@id":"https://fiveable.me/combinatorics/key-terms/floyd-warshall-algorithm#term"},"audience":{"@type":"EducationalAudience","educationalRole":"student"},"dateModified":"2026-07-03T02:21:06.613Z","isPartOf":{"@type":"Collection","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"},"publisher":{"@type":"Organization","name":"Fiveable","url":"https://fiveable.me"}},{"@type":"DefinedTerm","@id":"https://fiveable.me/combinatorics/key-terms/floyd-warshall-algorithm#term","name":"Floyd-Warshall Algorithm","description":"The Floyd-Warshall Algorithm is a dynamic programming method for finding shortest paths between every pair of vertices in a weighted graph. In Combinatorics, it shows up in graph theory and shortest-path problems.","url":"https://fiveable.me/combinatorics/key-terms/floyd-warshall-algorithm","inDefinedTermSet":{"@type":"DefinedTermSet","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"}},{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is Floyd-Warshall Algorithm in Combinatorics?","acceptedAnswer":{"@type":"Answer","text":"It is a dynamic programming algorithm for finding the shortest distances between all pairs of vertices in a weighted graph. In combinatorics, it belongs to graph theory and shortest-path algorithms. You usually represent the graph as a distance matrix and update it by checking possible intermediate vertices."}},{"@type":"Question","name":"How does Floyd-Warshall Algorithm work?","acceptedAnswer":{"@type":"Answer","text":"Start with a matrix of direct edge weights, using infinity where no edge exists. Then let each vertex act as a possible middle point and see whether going through that vertex shortens any path. If d(i, k) + d(k, j) is smaller than d(i, j), you replace the old value."}},{"@type":"Question","name":"Can Floyd-Warshall Algorithm handle negative weights?","acceptedAnswer":{"@type":"Answer","text":"Yes, it can handle negative edge weights as long as there is no negative weight cycle. That is one reason it stands out from some other shortest-path methods. If a negative cycle exists, the notion of a shortest path breaks because you can keep looping to lower the total cost."}},{"@type":"Question","name":"What is the difference between Floyd-Warshall and a single-source shortest path algorithm?","acceptedAnswer":{"@type":"Answer","text":"Floyd-Warshall solves the all-pairs version, so it gives shortest distances between every pair of vertices. A single-source algorithm starts from one vertex and finds the best routes from that source to the rest of the graph. If you need a full matrix of distances, Floyd-Warshall is the fit."}}]},{"@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Combinatorics","item":"https://fiveable.me/combinatorics"},{"@type":"ListItem","position":2,"name":"Key Terms","item":"https://fiveable.me/combinatorics/key-terms"},{"@type":"ListItem","position":3,"name":"Unit 14","item":"https://fiveable.me/combinatorics/unit-14"},{"@type":"ListItem","position":4,"name":"Floyd-Warshall Algorithm"}]}]} ```