Skip to content

Instantly share code, notes, and snippets.

@alieseparker
Created October 23, 2014 16:12
Show Gist options
  • Save alieseparker/45838d838f3593aea3f5 to your computer and use it in GitHub Desktop.
Save alieseparker/45838d838f3593aea3f5 to your computer and use it in GitHub Desktop.
class Warshall
def initialize(adjacencyMatrix)
@adjacencyMatrix=adjacencyMatrix
end
def getPathMatrix
numNodes=@adjacencyMatrix[0].length
pathMatrix=Array.new(@adjacencyMatrix)
for k in 0...numNodes
for i in 0...numNodes
#Optimization: if no path from i to k, no need to test k to j
if pathMatrix[i][k]==1 then
for j in 0...numNodes
if pathMatrix[k][j]==1 then
pathMatrix[i][j]=1
end
end
end
end
end
return pathMatrix
end
@daliborfilus
Copy link

Your optimization is not working. All jumps across 2 nodes (searching for path from a -> d in graph a -> b, b -> c, c ->d) will fail.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment