How is the Warshall algorithm different from Floyd algorithm in python?

Question

I have school assigment to do both of them using adjacency matrix, but almost every google search only shows the floyd-warshall as one algorithm. I already have the code for only the floyd. Does someone know the Warshall-algorithm and what is the difference between these two?

Answer 1

Welcome to StackOverflow. I guess most of your Google researches yielded the Floyd-Warshall algorithm as a result. I hope the following will answer your question and clarify any doubts.

First of all, the Floyd-Warshall algorithm solves the All-Pairs Shortest Path (APSP) problem, where the goal is to find the shortest path between all pairs of nodes in a graph (in your case, represented as an adjacency matrix). The algorithm has this name because the researchers Stephen Warshall and Robert Floyd independently came up with a very similar strategy to solve APSP problem.

Actually, the original Warshall's algorithm is simpler, since it only finds the transitive closure of a graph, and it doesn't use any information about the edge weights. Floyd's algorithm is basically this algorithm with additional considerations about such weights.

Given an n x n adjacency matrix G representing a directed graph, its transitive closure is a boolean n x n matrix where the entry at (i, j) is equal to true if and only if there is a directed path from vertex i to vertex j. Warshall's algorithm finds this transitive closure by repeatedly computing adjacency matrices, one for each vertex. Let us call W^k such matrices, where 0 <= k <= n. W^0 represents paths without any intermediate vertices, W^n has entries set to true when there is a path between the vertices having intermediate vertices from any vertex of the graph. The algorithm is the following:

def warshall(G):
  '''The graph G may be represented by means of a numpy matrix'''

  W = G  # this would be W^0
  n = len(G)
  for k in range(n):
    for i in range(n):
      for j in range(n):
        # (*)
        G[i, j] = G[i, j] or (G[i, k] and G[k, j])

  return W  # this would be W^n

For Floyd's algorithm, the input graph should be represented as a weighted adjacency matrix, and it's exactly like Warshall's, but with the (*) line changed as G[i, j] = min(G[i, j], G[i, k] + G[k, j]). The minimum is used because the goal is to minimize the overall weight.