## Introduction

Prerequisites: Shortest Path, Dynamic Programming

Floyd Warshall is a algorithm for finding the shortest distances between all pairs of nodes in a graph. The algorithm has a runtime of O(n3) and is able to detect cycles.

## Implementation

Floyd-Warshall uses a dynamic programming approach to finding the shortest path between node A and node B. Every path from node A to node B can be rewritten as a path from A to some node in between plus the path from the node in between to node B. The shortest path from A to B can be found by finding a node C such that the shortest path from A to C plus the shortest path from C to B is minimized.

### Formalization

Here is a recursive definition of the Floyd-Warshall algorithm:

```Given a directed graph with N nodes and edges between nodes:
Let edge(i,j) be the weight of the edge from node i to node j in the graph
Let shortestPath(i,j) be the shortest path from i to j

Base Case:
shortestPath(i,i) = 0

Recursion:
shortestPath(i,j) =  minimum of:
minimum of (shortestPath(i,k) + shortestPath(k,j) for all unvisited nodes k)
edge(i,j) if exists
```

### Code

```class edge {
int weight, source, dest;
public edge(int source, int dest, int weight) {
this.source = source;
this.dest = dest;
this.weight = weight;
}
}
public static final int UNDEFINED = Integer.MIN_VALUE;

public static int[][] FloydWarshall(Vector<Vector<edge>> adjList) {
// Let dist[i][j] be the minimum distance from i to j.
int[][] dist = new int[n][n];

// Initialize all minimum distances to be undefined.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = UNDEFINED;
}
}

// The minimum distance from a node to itself is 0.
for (int i = 0; i < n; i++) {
dist[i][i] = 0;
}

// Set distances for each edge.
for (int i = 0; i < n; i++) {
for (int j = 0; j < adjList.get(i).size(); j++) {
dist[e.source][e.dest] = e.weight;
}
}

// Iterate through each intermediate node.
for (int k = 0; k < n; k++) {
// Iterate through each starting node.
for (int i = 0; i < n; i++) {
// Iterate through each ending node.
for (int j = 0; j < n; j++) {
// If there is a path from i to k and k to j.
if (dist[i][k] != UNDEFINED && dist[k][j] != UNDEFINED) {
// Distance from i to j is distance from i to k plus distance from k
// to j.
int newDist = dist[i][k] + dist[k][j];
// Update distance from i to j, if the new distance is less than
// current distance or if there is no existing path from i to j.
if (dist[i][j] > newDist || dist[i][j] == UNDEFINED) {
dist[i][j] = newDist;
}
}
}
}
}
// Check if there are negative cycles.
for (int i = 0; i < n; i++) {
// If the distance from a node to itself is negative, then there is a
// negative cycle.
if (dist[i][i] < 0) {
System.out.println("negative cycle");
}
}

return dist;
}
```

## Exercises

1. Prove Floyd Warshall works.
2. Extend Floyd Warshall to return the order of nodes in a shortest path from the start to end (e.g. A→B→C)..