def floyd_warshall(matrix):
    """
    Find the shortest path between each pair of locations using the O(n^3) Floyd-Warshall algorithm:
    https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
    """
    for k in range(len(matrix)):
        for i in range(len(matrix)):
            for j in range(len(matrix)):
                # pick shorter out of path from i->j or i->k->j
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

    return matrix