4
\$\begingroup\$

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] > 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("Edge \t\t Distance \t Shortest Path")
    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("(%d, %d) \t\t %2d \t\t %s"
                      % (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()
\$\endgroup\$
5
\$\begingroup\$

FMc has made some excellent points. I'll try not to repeat those.

Vertices

You determine the list of vertices using:

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

and then repeatedly use len(vertices) through-out your code.

FMc suggests using:

    vertices = set(col[i] for col in graph for i in (0, 1))
    n = len(vertices)

Both implementations use sets to form a cover of all vertices. But this doesn't really make any sense. You're using range(len(vertices)) to determine the indices. What if the graphs used the vertices 1, 2, 4, & 5? Your sets would be {1, 2, 4, 5}, the length of the set is 4, and range(4) produces the indices 0, 1, 2, and 3. But you execute:

    for source, destination, weight in graph:
        distance[source-1][destination-1] = weight

you'd find source or destination is 5, compute subtract 1, to get the index 4, and find you've fallen off the end of the matrix!

Clearly, there is a requirement that all indices from 1 to N must be used, with no gaps allowed. But then, you don't need a set. You just need to find the maximum index.

    n = max(edge[col] for edge in graph for col in (0, 1))

Indexing is slow

In this code, for 100 vertices, how many times is distance[i] evaluated? How about distance[k]?

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

distance[i] is looked up somewhere between 2000000 and 4000000 times? Seems excessive, perhaps? distance[k] is looked up between 1000000 and 2000000 times. A wee bit less, but still quite a few.

Once you've entered the first for loop k is a constant for that iteration. You could lookup distance[k] once. Similarly, once you've entered the second for loop, i is a constant for that iteration. You could lookup distance[i] once.

    for k in range(len(vertices)):
        distance_k = distance[k]
        for i in range(len(vertices)):
            distance_i = distance[i]
            for j in range(len(vertices)):
                if distance_i[j] > distance_i[k] + distance_k[j]:
                    distance_i[j] = distance_i[k] + distance_k[j]
                    next_vertices[i][j]  = next_vertices[i][k]

Now, were looking up distance[k] only 100 times, and distance[i] only 10000 times. This will be a speed improvement.

We can do the for loops better: getting the indices and looking up the values together, using enumerate, and looping over the rows of the distance matrix:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            for j in range(len(vertices)):
                if distance_i[j] > distance_i[k] + distance_k[j]:
                    distance_i[j] = distance_i[k] + distance_k[j]
                    next_vertices[i][j]  = next_vertices[i][k]

Again, distance_i[k] does not change in the inner loop, so we can look it up once in the middle loop:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            dist_ik = distance_i[k]
            for j in range(len(vertices)):
                dist_ik_kj = dist_ik + distance_k[j]
                if distance_i[j] > dist_ik_kj:
                    distance_i[j] = dist_ik_kj 
                    next_vertices[i][j]  = next_vertices[i][k]

Finally, we can iterate over the distance_k row of the matrix, to avoid addition lookup overheads:

    for k, distance_k in enumerate(distance):
        for i, distance_i in enumerate(distance):
            dist_ik = distance_i[k]
            for j, dist_kj in enumerate(distance_k):
                dist_ik_kj = dist_ik + dist_kj
                if distance_i[j] > dist_ik_kj:
                    distance_i[j] = dist_ik_kj 
                    next_vertices[i][j]  = next_vertices[i][k]

Both next_vertices[i] and next_vertices[i][k] are constant in the inner loop; we could look them up once in the middle loop, for additional savings. You could even zip distance and next_vertices together in the for i, ... statement and look up both distance_i and next_vertices_i simultaneously. But perhaps that is getting a little too advanced.

Memory

Python lists are memory hogs. This doesn't matter if your graphs don't have more than a few hundred vertices. But if you want to support larger graphs (thousands of vertices? hundreds of thousands of vertices?), you'll want to use memory efficient structures.

You could use numpy to create your NxN distance and next_vertices matrices. But if you don't have numpy installed, we don't have to use that sledgehammer. Python does come with more memory efficient array objects, which can only store scalar information (integers, floats, characters) instead of the Jack-of-all-Trade heterogeneous lists of lists.

next_vertices hold integer vertex values. Instead of:

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

consider:

zeros = [0] * len(vertices)
next_vertices = [array.array('I', zeros) for _ in range(len(vertices))]

The rest of the code wouldn't need to change. You still access the data like next_vertices[i][j].

This creates a list of array integers, where the array takes a mere 2 bytes per value, instead of 8 bytes per element, plus the storage requirement of each integer (around 28 bytes each).

You can do something similar for the distance matrix. But now we need to know: are the weights always integer values, or are they floating point? You might want to use the the 'd' type code, if weights can be fractional. See the array for details.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Another point: when constructing the distance matrix, you should not use INF = sys.maxsize. That was valid in python 2 but not in 3. It is not guaranteed to return the largest int size. Try replacing INF with float('inf') instead. See stackoverflow.com/questions/7604966/… \$\endgroup\$ – Joe Aug 29 at 14:18
  • 1
    \$\begingroup\$ @Joe A good point. Good enough that it should be it's own independent answer that you can gain reputation from, instead of a comment where you don't. But math.inf is preferable to float('inf'). \$\endgroup\$ – AJNeufeld Aug 29 at 15:03
  • 1
    \$\begingroup\$ @Joe I went through the link and sys.maxsize is valid in python 3, and sys.maxint is valid in python 2. Since I'm on python3.x, I used the former. Strongly agree on math.inf. \$\endgroup\$ – Saurabh Aug 29 at 17:01
  • 1
    \$\begingroup\$ @Saurabh you're right I was thinking of sys.maxint. Still a good practice to use float('inf'). \$\endgroup\$ – Joe Sep 5 at 3:30
6
\$\begingroup\$

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 "paragraphs" 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] > 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)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ In python 3 ‘range’ is an iterator, so rng will be exhausted after the first use. \$\endgroup\$ – Maarten Fabré Aug 29 at 18:32
  • \$\begingroup\$ @MaartenFabré Try it in a Python REPL and I think you'll be surprised. For example: rng = range(3) ; print(list(rng)) ; print(list(rng)) ; print(rng[1]). Or next(rng), which will fail, because a range is not an iterator. There's probably a more authoritative way to prove the point, but those practical usages convince me. \$\endgroup\$ – FMc Aug 29 at 19:31
  • \$\begingroup\$ @MaartenFabré A range() is an iterable, not an iterator. It is reusable in exactly the same way a list is reusable; you can iterate over them multiple times, even simultaneously in parallel threads. \$\endgroup\$ – AJNeufeld Aug 29 at 20:03
  • 1
    \$\begingroup\$ :facepalm: that's what you get by replying on your phone without checking... \$\endgroup\$ – Maarten Fabré Aug 29 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.