MATLAB Answers

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

135 views (last 30 days)
Yang Feiming
Yang Feiming on 3 Dec 2019
Commented: Bruno Luong on 24 Aug 2020 at 17:41
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!

  0 Comments

Sign in to comment.

Answers (3)

Bruno Luong
Bruno Luong on 22 Aug 2020 at 11:33
Edited: Bruno Luong on 24 Aug 2020 at 17:34
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.
%
% See also: graph, digraph, TestAllShortestPaths
%
% 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
A = G.adjacency('weight');
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

  10 Comments

Show 7 older comments
Rub Ron
Rub Ron on 24 Aug 2020 at 17:01
@Bruno. For previous G, check spath{6}{:}
It gives one path: 1 4 5 6
instead of two paths:
1 4 5 6
1 2 3 4 5 6
Rub Ron
Rub Ron on 24 Aug 2020 at 17:37
s = [1 1 2 3 1 4 5];
t = [2 2 3 4 4 5 6];
G = graph(s,t);
G.Edges.Weight = [1 1 3 1 1 1 1]';
[~,spath] = BellmanFord(G,1);
spath{6}{:}
Output: (perhaps a unique is missing)
ans =
1 4 5 6
ans =
1 2 3 4 5 6
ans =
1 4 5 6
ans =
1 2 3 4 5 6
ans =
1 4 5 6
ans =
1 2 3 4 5 6
ans =
1 4 5 6
ans =
1 2 3 4 5 6
Bruno Luong
Bruno Luong on 24 Aug 2020 at 17:41
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

Sign in to comment.


Koushik Kureti
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

  0 Comments

Sign in to comment.


Walter Roberson
Walter Roberson on 21 Aug 2020 at 23:54
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.

  0 Comments

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!