Shortest path with condition

Hi all.

I have this piece of code :

W = [4 3 6 2 4 5 3 3 6 1 3 5 5 2 4 7 7 3 5 4];
DG = sparse([1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5],...
    [2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 ],W);
g = digraph(DG);
% Construct all possible ways that we could traverse all nodes, starting at 
% node 1 and ending at node 1 : 
paths = perms(2:5);
paths = [ones(size(paths, 1), 1) paths];
% Check if a path is feasible (edges exist between all node pairs), and how 
% long it is 
dist = NaN(size(paths, 1), 1);
for ii=1:size(paths, 1)
      path = paths(ii, :);
      edgeID = findedge(g, path(1:end), path([2:end 1]));
      if all(edgeID ~= 0)
          dist(ii) = sum(g.Edges.Weight(edgeID));
      end
end
[shortest_path_distance, id] = min(dist)
mypath = paths(id, :)
p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, mypath([1:end 1]), 'EdgeColor', 'magenta')

I try to calculate the shortest path according to the matrices I create. There is only one condition: I want to exclude any path in which node 2 is before node 5. Do I have to enter a condition inside the for's IF?

Thank you!

[Ameer Hamza]

What do you mean by ' node 2 is before node 5' since your path is circular. Before and after makes no sense unless defined properly. If you mean node 2 should not be before node 5 in the first round, then you can refer to my answer.

Answer 1

[Ameer Hamza]

Instead of adding a condition inside for loop, it is better to delete rows from paths matrix in which node 2 is occurring before node 5. You will see that several paths can be immediately ignored, that will also save computation inside for loop.

ind = find(paths' == 2) < find(paths' == 5);
paths(ind, :) = [];