54 views (last 30 days)

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.

%

% 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
on 24 Aug 2020

@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
on 24 Aug 2020

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
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.

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

Start Hunting!
## 0 Comments

Sign in to comment.