Floyd-Warshall Path Reconstruction Below is the implementation for the Floyd-Warshall algorithm, which finds all-pairs shortest paths for a given weighted graph.
The function floyd_warshall takes a graph as an input, which is represented by an edge list in the form of [source, destination, weight]
The path_reconstruction function outputs the shortest paths from each vertex that is connected to every other vertex.
Please provide suggestions for improvements of any sort.
import sys

INF = sys.maxsize

def floyd_warshall(graph):
    source_vertices = [column[0] for column in graph]
    destination_vertices = [column[1] for column in graph]
    vertices = list(set(source_vertices) | set(destination_vertices))

    distance = [[INF] * len(vertices) for i in range(len(vertices))]
    next_vertices  = [[0]   * len(vertices) for i in range(len(vertices))]

    for i in range(len(vertices)):
        distance[i][i] = 0
    for source, destination, weight in graph:
        distance[source-1][destination-1] = weight
        next_vertices[source-1][destination-1] = destination-1

    for k in range(len(vertices)):
        for i in range(len(vertices)):
            for j in range(len(vertices)):
                if distance[i][j] &gt; distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
                    next_vertices[i][j]  = next_vertices[i][k]

    path_reconstruction(distance, next_vertices)

def path_reconstruction(dist, nxt):
    print(&quot;Edge \t\t Distance \t Shortest Path&quot;)
    for i in range(len(dist)):
        for j in range(len(dist)):
            if i != j:
                path = [i]
                while path[-1] != j:
                    path.append(nxt[path[-1]][j])
                print(&quot;(%d, %d) \t\t %2d \t\t %s&quot;
                      % (i + 1, j + 1, dist[i][j], ' - '.join(str(p + 1) for p in path)))
    print()

def main():
    edge_list1 = [
        [1, 3, -2],
        [2, 1, 4],
        [2, 3, 3],
        [3, 4, 2],
        [4, 2, -1]
    ]
    edge_list2 = [
        [1, 2, 10],
        [1, 3, 20],
        [1, 4, 30],
        [2, 6, 7],
        [3, 6, 5],
        [4, 5, 10],
        [5, 1, 2],
        [5, 6, 4],
        [6, 2, 5],
        [6, 3, 7],
        [6, 5, 6]
    ]

    floyd_warshall(edge_list1)
    floyd_warshall(edge_list2)

if __name__ == '__main__':
    main()
Your program provides a good example for seeing how one can increase code readability through some common techniques: (1) convenience variables to avoid verbose repetition; (2) code organized as small commented &quot;paragraphs&quot; or blocks; and (3) the use of shorter variables names to lighten the visual weight of the code, thus enhancing ease of reading and visual scanning. Note that short names must be used judiciously: because they can be cryptic, short vars typically
derive their meaning either from a consistently used convention in the program
or from other contextual clues (eg, from nearby functions or collections having more explicit names and from well-placed comments). Here's a heavily edited version of floyd_warshall() along those lines. Because I'm lazy, I will assume that you implemented Floyd-Warshall correctly.
def floyd_warshall(graph):
    # Collect all vertices.
    vertices = set(
        col[i]
        for col in graph
        for i in (0, 1)
    )
    n = len(vertices)
    rng = range(n)

    # Initialize the distance and next-vertex matrix.
    dists = [
        [0 if i == j else INF for j in rng]
        for i in rng
    ]
    next_vertices = [
        [0 for j in rng]
        for i in rng
    ]

    # Populate the matrixes.
    for src, dst, weight in graph:
        i = src - 1
        j = dst - 1
        dists[i][j] = weight
        next_vertices[i][j] = j

    # Do that Floyd-Warshall thing.
    for k in rng:
        for i in rng:
            for j in rng:
                ikj = dists[i][k] + dists[k][j]
                if dists[i][j] &gt; ikj:
                    dists[i][j] = ikj
                    next_vertices[i][j]  = next_vertices[i][k]

    return path_reconstruction(dists, next_vertices)

A bigger issue is that your floyd_warshall() function should not be calling a
function that prints. Rather it should return some kind of meaningful data.
That approach makes your function more readily testable. For example,
path_reconstruction() could return a list of declarative dicts.
def path_reconstruction(dists, next_vertices):
    # Same ideas here: return data, don't print; use convenience
    # vars where they help with readability.
    rng = range(len(dists))
    paths = []
    for i in rng:
        for j in rng:
            if i != j:
                path = [i]
                while path[-1] != j:
                    path.append(next_vertices[path[-1]][j])
                paths.append(dict(
                    i = i,
                    j = j,
                    dist = dists[i][j],
                    path = path,
                ))
    return paths

Then do your printing outside of the algorithmic code.
def main():
    edge_lists = [
        [
            [1, 3, -2],
            [2, 1, 4],
            [2, 3, 3],
            [3, 4, 2],
            [4, 2, -1],
        ],
        [
            [1, 2, 10],
            [1, 3, 20],
            [1, 4, 30],
            [2, 6, 7],
            [3, 6, 5],
            [4, 5, 10],
            [5, 1, 2],
            [5, 6, 4],
            [6, 2, 5],
            [6, 3, 7],
            [6, 5, 6],
        ],
    ]
    for el in edge_lists:
        paths = floyd_warshall(el)
        for p in paths:
            print(p)