floyd_warshall

Ali Hamdi Ali Fadel · @AliOsm · almost 3 years

Floyd-Warshall (all pairs shortest path) algorithm implementation.

def floyd_warshall(graph_weights_matrix)
n = graph_weights_matrix.size
graph_weights_matrix.each do |row|
raise ArgumentError.new 'The given matrix should be a square matrix' if row.size != n
end
n.times do |k|
n.times do |i|
n.times do |j|
if graph_weights_matrix[i][j] < graph_weights_matrix[i][k] + graph_weights_matrix[k][j]
graph_weights_matrix[i][j] = graph_weights_matrix[i][j]
else
graph_weights_matrix[i][j] = graph_weights_matrix[i][k] + graph_weights_matrix[k][j]
end
end
end
end
graph_weights_matrix
end
0 · 3 · 1
Emad Elsaid · @emad-elsaid · almost 3 years

I checked out the implementation written on wikipedia, and I see your implementation is using K as the innermost loop, I think that alter the algorithm behavior. https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

  1. so first lets use K as the outermost loop.
  2. instead of creating an array and getting the minimum this has a higher cost than using a normal If condition at the end of the line.
  3. use “do…end” instead of curly braces becuase it’s a multiline block.
  4. guard the function to prevent input that’s not square matrix

Thanks for mentioning the issue in the loop variables! I didn’t recognize it while writing. The great thing that it worked for the example I tried :3 I liked point number 4 :)