Ali Hamdi Ali Fadel
· @AliOsm
·
almost 4 years

Any ideas on how to improve to implementation?

Ali Hamdi Ali Fadel · @AliOsm · almost 4 years

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

def floyd_warshall(graph_weights_matrix)n = graph_weights_matrix.sizegraph_weights_matrix.each do |row|raise ArgumentError.new 'The given matrix should be a square matrix' if row.size != nendn.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]elsegraph_weights_matrix[i][j] = graph_weights_matrix[i][k] + graph_weights_matrix[k][j]endendendendgraph_weights_matrixend

0 ·
3 ·
1

Ali Hamdi Ali Fadel
· @AliOsm
·
almost 4 years

Any ideas on how to improve to implementation?

Emad Elsaid
· @emad-elsaid
·
almost 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

- so first lets use K as the outermost loop.
- 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.
- use “do…end” instead of curly braces becuase it’s a multiline block.
- guard the function to prevent input that’s not square matrix

Ali Hamdi Ali Fadel
· @AliOsm
·
almost 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 :)