Floyd Warshall

Floyd-Warshall is an all-pairs shortest path algorithm which runs in time. It is a very simple algorithm, requiring only four or five lines in most implementations. It requires a matrix for the distances between two points, so an adjacency matrix is a good choice here. It works by considering optimal paths through a middle vertex. Quite remarkably, if the iteration is done in the correct order, only one iteration is required.

C++

dist[a][b] contains the current shortest distance from a to b. The graph is V vertices, labeled 0 to V-1.

for(int k = 0; k < V; k++)
    for(int i = 0; i < V; i++)
        for(int j = 0; j < V; j++)
            if(dist[i][k] + dist[k][j] < dist[i][j])
                dist[i][j] = dist[i][k] + dist[k][j];

C++ 2

This code uses deprecated language, but fits into four lines. This currently does work on USACO's grader.

for(int k = 0; k < V; k++)
    for(int i = 0; i < V; i++)
        for(int j = 0; j < V; j++)
            dist[i][j] <?= dist[i][k] + dist[k][j];