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

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!

Answer 1

[Bruno Luong]

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

[Rub Ron]

how would you edit your code to make it work for graphs with string node names?

[Bruno Luong]

The code works regardless the node name is defined or not.

Node name is just a label. I just don't care.

[Walter Roberson]

Is the question about the ability to specify the source and destination nodes by label instead of by number ?

[Rub Ron]

@Walter Roberson. Yes. But I think a work around is to use findnode(G,'nodeName') which give you the node index and use this as the input of Bruno's function.

[Rub Ron]

@Bruno "EDIT and warning rather use the version on the comment that has bug fixed" What is the fixed bug? the code you provided initially seems to work

[Bruno Luong]

The error occurs in case of weighted graph. The first code might return some extra path that is not shortest.

Example:

s = [1 1 2];
t = [2 3 3];
w = [1 5 1];
G = graph(s,t,w);
plot(G);
A = G.adjacency('weight');

The shorttest path from 1 to 3 is (1-2-3) with the distance 2.

If I run the bug fix version with this graph

source = 1;
[d, spath] = BellmanFord(A, source);
for k=1:length(spath)
    spk = spath{k};
    fprintf('shorttest path from %d to %d is(are):\n', source, k)
    for i=1:length(spk)
        fprintf('\t%s\n', mat2str(spk{i}));
    end
end

it reports correctly

shorttest path from 1 to 1 is(are):
	1
shorttest path from 1 to 2 is(are):
	[1 2]
shorttest path from 1 to 3 is(are):
	[1 2 3]

It I run the first version of the code it reports

...
shorttest path from 1 to 3 is(are):
	[1 3] % <= this is wrong, since the path length is 5 (> 2)
	[1 2 3]

I could fix both but I decide not to maintain the first version.

I'll edit out the buggy version after some time.

[Rub Ron]

@Bruno, thanks for the explanation.

[Rub Ron]

@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]

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]

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

Answer 2

[Koushik Kureti]

Hello Yang Feiming,

You can use graph class in MATLAB, which has a shortest path method

https://www.mathworks.com/help/matlab/ref/graph.html

https://www.mathworks.com/help/matlab/ref/graph.shortestpath.html

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

Answer 3

[Walter Roberson]

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.