How can I get all the existing shortest paths between two single nodes for graph

47 views (last 30 days)
Yang Feiming on 3 Dec 2019
Commented: Bruno Luong on 24 Aug 2020
I konw that there are many functions can compute the distance between two nodes, and there are some functions can return the shortest path between two nodes, however, I find all the functions seem only return the first shortest path between two nodes, but I want to find a way to get all the existing shortest paths between two single nodes for graph. For instance, if we have a graph: (1,2), (1,3), (2,4), (3,4), when I query the shortest path between 1 and 4, it should return (1,2,4) and (1,3,4). Thanks!

Bruno Luong on 22 Aug 2020
Edited: Bruno Luong on 24 Aug 2020
Here is the code base on Bellman Ford algorithm which provides ALL shortest paths from a single node to ALL other nodes
s = [1 1 1 1 2 2 2 2 2 8 8 12 14 14 1 14];
t = [3 5 4 2 6 10 7 9 8 11 12 13 7 6 8 15];
G = graph(s,t);
[d,spath] = BellmanFord(G, 1); % function bellow
for k=1:length(spath)
spk = spath{k};
fprintf('shortest path from 1 to %d is(are):\n', k)
for i=1:length(spk)
fprintf('\t%s\n', mat2str(spk{i}));
end
end
Put this function in an mfile BellmanFord.m
function [d, spath] = BellmanFord(arg1, arg2)
% d = BellmanFord(A, start) OR
% d = BellmanFord(G, start)
%
% [d, spath] = BellmanFord(...)
%
% BellmanFord shortest paths
%
% INPUTS:
% A: (N x N) symmtric ajadcent matrix or
% G: graph/digraph object with N nodes
% start; interger in [1,N] start node
% OUTPUTS:
% d: (N x 1): array contains distance vector from start-node to all nodes
% spath: (N x 1) cell array. All shortest paths.
% For dest in [1,N] spath{dest} is a a row-cell contains all
% shortest paths (array of nodes) from start-node to dest-node.
%
%
% Author: brunoluong at yahoo dot findmycountry
if isa(arg1,'graph') || isa(arg1,'digraph')
G = arg1;
if ismultigraph(G)
edges = table2array(G.Edges);
ij = edges(:,1:2);
w = edges(:,3);
n = max(ij,[],'all');
A = accumarray(ij, w, [n,n], @min, 0, true);
if isa(arg1,'graph')
A = triu(A,1).'+A;
end
else
end
else
A = arg1;
end
if nargin < 2
start = 1; % starting node
else
start = arg2;
end
A = A.';
n = size(A,1);
start = max(min(start,n),1);
% initialize distance matrix
d = inf(n,1);
du = 0;
i = start;
if nargout < 2
% only distance is requested
while true
d(i) = du;
[i, j, dij] = find(A(:,i));
if isempty(i)
break
end
[du, p] = sort(du(j)+dij);
[i, p] = sort(i(p)); % here we requires stable sorting, which is the case with MATLAB
b = [true; diff(i,1,1)>0];
i = i(b);
du = du(p(b));
b = du < d(i);
i = i(b);
du = du(b);
end
else
% shortest paths requested
prev = cell(n,1);
neig = inf(1,n);
for c = 0:n-1
d(i) = du;
neig(i) = c;
jprev = i;
[i, j, dij] = find(A(:,jprev));
if isempty(i)
break
end
I = [i, du(j)+dij, jprev(j)];
I = sortrows(I, [1 2]);
dI = diff([0 0; I(:,1:2)],1,1) ~= 0;
change = find(dI(:,1)|dI(:,2));
Ic = I(change,:);
b = dI(change,1) & (Ic(:,2) <= d(Ic(:,1)));
lgt = diff([change; size(dI,1)+1],1,1);
I = I(repelem(b, lgt),:);
if isempty(I)
break
end
lgtk = lgt(b);
istart = cumsum([1; lgtk]);
istop = istart(2:end)-1;
istart(end) = [];
% keep track the previous visit nodes
% doing like jprev = mat2cell(I(:,3), lgtk, 1); without overhead
jprev = cell(size(istart));
j = I(:,3);
for k=1:size(jprev)
jprev{k} = j(istart(k):istop(k));
end
i = I(istart,1);
du = I(istart,2);
neq = du < d(i);
if all(neq) % optimization by not bother with CELLFUN
prev(i) = jprev;
else
prev(i(neq)) = jprev(neq);
eq = ~neq;
ieq = i(eq);
prev(ieq) = cellfun(@union, prev(ieq), jprev(eq), 'unif', 0);
end
end
% Second past to build shortest paths
spath = cell(size(prev));
spath{start} = {start};
[neig, k] = sort(neig);
k = k(2:find(isfinite(neig),1,'last'));
for n = k
spath{n} = cellfun(@(p) [p,n], cat(1, spath{prev{n}}), 'unif', 0);
end % for-loop
end % if of shortest paths branch
end % BellmanFord
Bruno Luong on 24 Aug 2020
Yes, I change VERTCAT with UNION in CELLFUN statement and it fixes the redundancy.
spath{6}{:}
ans =
1 4 5 6
ans =
1 2 3 4 5 6

Koushik Kureti on 5 Mar 2020
Hello Yang Feiming,
You can use graph class in MATLAB, which has a shortest path method
If it is a directed graph, you can use the digraph class instead.
If you want to find out shortest paths between all nodes in the graph, then the following link helps: https://www.mathworks.com/help/matlab/ref/graph.distances.html

Walter Roberson on 21 Aug 2020
Populate a column vector with a list of all of the source nodes to be considered. Call this L.
Loop:
Set NewL to empty.
Loop examining each row in L. Extract the last column of the row, which will be a node number, N. Look up the connections (output connections in case of a digraph) that N has, and remove from that set all nodes that already exist in the current row of L. Now for each remaining connected node, add the current row followed by the connected node, as an entry at the end of NewL; if you have run out of connected nodes that do not already appear in the current row then you would not be adding anything to NewL.
Once you are done examining all rows in L, set L = NewL.
Select all rows of L that end in any of the destination nodes. If there are none, then continue looping; otherwise, the outer loop.
End of outer loop.
Output list the list of rows in L that end in any of the destination nodes.
This algorithm can have multiple start nodes and multiple destination nodes, and will find all of the shortest paths of equal length between any of the start nodes and any of the destination nodes.
This algorithm is a "breadth first search" and can be implemented in terms of the bfsearch() operation.