30 Apr 2006
22 Oct 2008)
MatlabBGL provides robust and efficient graph algorithms for Matlab using native data structures.
function D = dijkstra_all_sp(G,optionsu)
% DIJKSTRA_ALL_SP Compute all pairs shortest path using repeated Dijkstras
% This algorithm runs a series of Dijkstra's shortest path problems to
% compute the all pairs shortest path matrix.
% Using one of the other algorithms is preferable, however, this algorithm
% is useful as a base when there are memory concerns with the other
% algorithms. For example, you could easily parallelize this algorithm to
% compute a subset of shortests paths on each processor and then aggregate
% the results.
% D = dijkstra_all_sp(G) produces identical output to
% load graphs/clr-26-1.mat
% D1 = floyd_warshall_all_sp(A)
% D2 = dijkstra_all_sp(A)
% See also ALL_SHORTEST_PATHS, JOHNSON_ALL_SP, FLOYD_WARSHALL_ALL_SP.
% TODO: Make the code work for dijkstra or bellman_ford
% 13 July 2007
% Implement the algorithm correct for transposed input
% First, transpose the graph so that Dijkstra's won't have to at each
options = optionsu;
options = struct('istrans',0);
G = G';
% Next, check to make sure a Dijkstra's call works so we don't have to
% check on the inner loop.
d_i = dijkstra_sp(G,1,options);
D = zeros(size(G));
D(:,vi-1) = d_i;
d_i = dijkstra_sp(G,vi,options);
% save the last one
D(:,end) = d_i;
D = D';