floyd_warshall

Ali Hamdi Ali Fadel · @AliOsm · about 4 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 · about 4 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
Ali Hamdi Ali Fadel · @AliOsm · about 4 years

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 :)