function [d, pi] = dag_shortest_paths(W, source)
% DAG_SHORTEST_PATHS Compute the shortest path from a source to each node i in a weighted DAG.
% [d, pi] = dag_shortest_paths(W, source)
%
% W(i,j) is the weight of the edge i->j. Edges can have -ve weight, but we assume there are no
% -ve weight cycles.
% d(i) = shortest distance from source to i
% pi(i) = predecessor of i on the shortest path to i
%
% See Cormen, Leiserson and Rivest, "An Intro. to Algorithms", p536

A = (W ~= inf); 
A = setdiag(A, 0);
order = topsort(A);
n = length(W);
d = zeros(1,n);
pi = zeros(1,n);

% initialize single source p520
for i=1:n
  d(i) = inf;
  pi(i) = -1;
end
d(source) = 0;

for u=order
  for v=neighbors(A, u)
    % relax(u,v,w) p520
    if d(v) > d(u) + W(u,v)
      d(v) = d(u) + W(u,v);
      pi(v) = u;
    end
  end
end
   
