floyd_warshall.m

best routing protocol

function [res, next_hop] = floyd_warshall(d)
%d is the NxN pairwise distance matrix
%no missing data in d, please
    N = length(d);
    
    next_hop = []; % next_hop(i,j) is from i->j, the id# for next hop

    for i=1:N
      for j=1:N
	if d(i,j)<inf
	  next_hop(i,j)=j;
	else
	  next_hop(i,j)=i;
	end
      end
    end
    
    new_d = d;
    for k = 1:N
        old_d = new_d;
        for i = 1:N
            for j = 1:N
                new_d(i,j)=min(old_d(i,j), old_d(i,k)+old_d(k,j));
		if old_d(i,j)>old_d(i,k)+old_d(k,j)
		  next_hop(i,j)=next_hop(i,k);
		end
            end
        end
    end
    res = new_d;