liveBook · Manning

Chapter 9: Floyd-Warshall Algorithm

What you will learn in chapter 9 of Algorithms Every Programmer Should Know

Introduces Floyd-Warshall as a dynamic-programming approach to finding exact shortest distances between every pair of nodes in a dense graph.

After this chapter you will be able to

What it builds on

Section by section

Introduction

Introduces Floyd-Warshall as a dynamic-programming approach to finding exact shortest distances between every pair of nodes in a dense graph.

Key terms: All-Pairs Shortest Path, dense graph, Dijkstra's algorithm, Floyd-Warshall, dynamic programming matrix, intermediate node, global lookup table

9.1 All-pairs shortest path (APSP)

The section explains how Floyd–Warshall builds an all-pairs shortest-path matrix by repeatedly testing each vertex as a possible intermediate stop.

Key terms: all-pairs shortest path, single-source, negative edge weights, initial distance matrix, A0, infinity, bridge node, intermediate, phase, dynamic programming

9.2 Real world applications

This section shows how precomputed Floyd-Warshall results support fast lookups in knowledge graphs and transit networks, while explaining why the approach is limited to bounded networks.

Key terms: cubic time, O(V3), dense network, precomputed matrix, Retrieval-Augmented Generation (RAG), semantic knowledge graphs, transitive closure, reachability, O(1) lookup table, nodes

9.3 Key insights

This section explains when Floyd-Warshall is useful, how it handles negative weights and reveals negative cycles, and how its fixed cost affects algorithm choice.

Key terms: negative edge weights, intermediate bridge (k), negative weight cycle, D[i][i] = 0, D[i][i] < 0, dense graph, sparse graph, O(V3), empty (∞) bridge paths, Single-Source

9.4 Summary

9.5 References

Where this is used later

Concepts explained in this chapter

← Chapter 8: Ant Colony Optimization Algorithm Chapter 10: Push Relabel Algorithm →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.