function d=matdijkstra(A,i)
% MATDIJKSTRA Dijkstra's shortest paths via matrix-vector products on a ring
%
% d = matdijkstra(A,i) returns the shortest paths for the graph with weighted
% adjacency matrix A and all edge weights are positive.  The graph must also
% be undirected.
%
% Examples:
%   % requires MatlabBGL

% David F. Gleich
% Purdue University Networks & Matrix Computations sample code
% 2011-09-08

n = size(A,1);

if size(A,1) ~= size(A,2), error('matdijkstra:argumentError',...
	'the input is not a square matrix'); end
if i<1 || i>n, error('matdijkstra:argumentError',...
	'the starting vertex %i is not in [1,%i]',i, n); end
	
d = Inf*ones(n,1); % all distances are infinite initially
d(i) = 0;

[src,dst,val] = find(A); % get the non-zeros so we can do the matvec ourselves

assert(all(val > 0));

for i=1:n
	dnew = Inf*ones(n,1);
	% implement the semi-ring "matvec" in triplet form.
	for nz=1:length(src)
	    dnew(src(nz)) = min(dnew(src(nz)),val(nz) + d(dst(nz)));
    end
	if all(dnew == d), break; end % things won't change next time
    d = min(dnew,d);
end	
