Floyd's algorithm is very closely related to Warshall's (as I previously presented here and here). Indeed it's sometimes called the Floyd-Warshall algorithm since Floyd apparently got the idea for it from Warshall's algorithm. It's also often called the all-pairs shortest-paths problem which is the descriptive version.
Floyd's algorithm is more commonly seen in the literature (a Google on Warshall is in fact brings this algorithm higher that Warshall's own). The reason for this is that it's useful in more applications. One often wants to know how far it is to something, say a network resource, rather than just whether or not one can get there.
The way Floyd's algorithm works is so. We start with a weight matrix of a directed graph, which is like the adjacency matrix except that it contains "weights" of edges representing distances between nodes. As with Warshall's algorithm one then iterates through intermediate nodes, call them k, to find the distance of the path between each node i,j through k. If it is smaller than the distance already calculated through a previous k, and smaller than the weight (distance) of any edge connected i to j, then the current distance in the distance matrix is replaced with the new, shorter, distance. Note that in my version I initialize the distance matrix with the weight matrix so we always compare the distance paths with, at least, the direct distance between the nodes. We might call this k=0 (or maybe k=-1 would be better given my 0 indexed arrays).
One thing I didn't note in my discussion of Warshall's algorithm is that both these algorithms are examples of dynamic programming. In dynamic programming one builds a final result from intermediate results. I this case each intermediate result is the intermediate node, k. Since we iterate through each k we build up successively all possible paths from all nodes using all possible intermediate nodes thus comparing all paths between all nodes to find the smallest.
OK, so here's the algorithm. Enjoy. (Oh, I included a randomized again, so its easy to generate lots of examples.)
class Floyd #aka all-pairs shortest paths algorithm
def initialize(weightMatrix=nil,oo=256) #256?
@weightMatrix=weightMatrix
@oo=oo #needed to set a weight considered "infinite"
end
attr_accessor :oo
attr_accessor :weightMatrix
def getDistanceMatrix
numNodes=@weightMatrix[0].length
distanceMatrix=Array.new(@weightMatrix)
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 distanceMatrix[i][k]<@oo then
for j in 0...numNodes
distance = distanceMatrix[i][k] + distanceMatrix[k][j]
if distance<distanceMatrix[i][j] then
distanceMatrix[i][j]=distance
end
end
end
end
end
distanceMatrix
end
def showDistanceMatrix
puts "weight"
@weightMatrix.each{|c| print c.to_s.gsub(@oo.to_s,"oo"),"\n"}
puts "distance"
getDistanceMatrix.each{|c| print c.to_s.gsub(@oo.to_s,"oo"),"\n"}
end
end
#tests:
if __FILE__ == $0
floyd=Floyd.new
oo=floyd.oo
floyd.weightMatrix=[[0,oo,3,oo],[2,0,oo,oo],[oo,7,0,1],[6,oo,oo,0]]
floyd.showDistanceMatrix
dim=10 #randomize out a big graph
weightMatrix=Array.new(dim){Array.new(dim)}
for i in 0...dim do
for j in 0...dim do
if i==j then
weightMatrix[i][j]=0
elsif rand(dim/2)==0 then
weightMatrix[i][j]=rand(9)+1
else
weightMatrix[i][j]=oo
end
end
end
floyd.weightMatrix=weightMatrix
floyd.showDistanceMatrix
end
