MATLAB Answers

1

Shortest path through node group sets

Asked by Skylar Cox on 9 Nov 2019 at 21:12
Latest activity Commented on by Christine Tobler about 23 hours ago
I am trying to find the maximum path through a series of nodes. I have forumulated the problem as a shortest path problem using negative weights for distances between nodes. Node sets are grouped and I want to find a path that only passes through one node of each group. For example, nodes are labeled as start (s) and end (e) and A1, A2, B1, B2, C1, and C2. If a path passes through A1, it cannot pass back through A2. The node groups represent a task that is to be accomplished (letter indicator) while the numeric value indicates a time. This means that task A can be accomplished at two different times but not both. The figure is included for additional information.
I originally started using the 'shortestpath' function in matlab but realized it was revisiting tasks. Are there any algorithms out there that I should look into?

  0 Comments

Sign in to comment.

3 Answers

Walter Roberson 님의 답변 9 Nov 2019 21:26

shortest path with negative weights is subject to looping.
You should instead use weights that are the maximum weight plus 1, minus the existing weights.

  2 Comments

Skylar Cox on 9 Nov 2019 at 21:41
I have constructed the graphs such that they are acyclic. The 'isdag' function verifies it. I don't have any loops but rather re-visiting node groups that I need to avoid.
Sorry, I did not notice the groups of nodes part before.
For situations like this, you need to work incrementally creating augmented directed graphs.
When you are at S, you have a choice of going to A1. You find the subgraph of all of the places you can get to from A1, and you clone that subgraph into new nodes but with the links back to other members of A deleted, and replace the S -> A1 link with a link from S to that cloned graph. And you do similar things for the other groups, recursively. This can lead to a bunch of branching.
So instead of S -> A1 -> {B1, B2, C3, C4} you would have S -> newA1 -> {A1B1, A1B2, A1C3, A1C4} where A1B1 is like B1 but there is no A1B1 -> A2 link, just A1B1 -> {A1C3, A1C4}
Once S has traversed to newA1 that is disconnected from the previous A1 subtree, then because it is a directed graph, there is no cross-link possible to reach something that could get to a different member of the A group.
Yes, the number of nodes can increase by a fair bit. There might be ways to reduce the branching in some cases.
This approach might perhaps sound too made-up-on-the-spot, but it is similar to the approach that is used to convert Non-Deterministic Finite Automata (NDFA) into Deterministic Finite Automata (DFA), by following all of the paths "simultaneously". A cross-product of states ends up being created, which is the sort of thing that is a nuisance if you are trying to work everything out by hand, but which you can hand over to computers to compute all of.

Sign in to comment.


Answer by Thiago Henrique Gomes Lobato on 10 Nov 2019 at 10:24

If you have negative weightings an Algorithm that would work to find the shortest path is the Bellman-Ford. You can find some information for it (as well as some example implementations) here https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/ . There's also some matlab implementations in file exchange https://de.mathworks.com/matlabcentral/fileexchange/38129-the-bellman-ford-moore-shortest-path-algorithm

  1 Comment

Thanks but the suggested algorithm will still allow for revisiting node groups (e.g. A1 and A2). I need something that will find the shortest path but never visit one group more than a single time.

Sign in to comment.


Answer by Christine Tobler on 11 Nov 2019 at 12:53

There is no direct graph-based algorithm to solve this. I would suggest using the optimization toolbox to define this as an optimization problem. Here's an example:
n = 14;
rng default;
g = digraph(triu(sprand(n, n, 0.3), 1));
g = reordernodes(g, randperm(n));
g.Edges.Weight(findedge(g, 14, 10)) = 0.2;
s = 13; e = 11;
path = shortestpath(g, s, e)
A = adjacency(g, 'weight');
tsp = optimproblem;
edges = optimvar('edges',size(A),'Type','integer','LowerBound',0,'UpperBound',1);
tsp.Constraints.Start = sum(edges(s, :)) == 1;
tsp.Constraints.End = sum(edges(:, e)) == 1;
tsp.Constraints.OnlyExisting = edges.*(A==0) == 0;
intermediateEdges = setdiff(1:numnodes(g), [s e]);
tsp.Constraints.InputEqualOutput = sum(edges(:, intermediateEdges)) == sum(edges(intermediateEdges, :), 2)';
tsp.Constraints.MaxOnePassThroughNode = sum(edges, 1) <= 1;
tsp.Objective = -sum(A.*edges, 'all');
tspsol = solve(tsp);
sg = digraph(tspsol.edges)
figure(1)
p = plot(g);
highlight(p, sg)
% Additional objective: Don't use two nodes from the same group (here,
% let's say 3 and 14 are in the same group):
group = [3 14]
% Allow exactly one outgoing edge among all edges coming out of all nodes
% in the group:
tsp.Constraints.Group = sum(edges(:, group), 'all') <= 1;
tspsol2 = solve(tsp);
sg2 = digraph(tspsol2.edges)
figure(2)
p = plot(g);
highlight(p, sg2)
Every group of nodes can be added as an additional constraint to this formulation.
Note one potential problem with this is that the constraints just say that every node except the start and end node must have as many in-edges as out-edges. If the graph wasn't acyclic, this would mean that it's possible to have a disconnected cycle of nodes that doesn't connected to the path from the start to the end node.
Another possible concern is performance: Calling intlinprog with a numnodes(g)-by-numnodes(g) variable to optimize could be significantly slower than the shortestpath method, for larger graphs.

  2 Comments

Excellent. This makes sense. However, when I run the code above, I get an error on the following line:
tsp.Constraints.OnlyExisting = edges.*(A==0) == 0;
I'm not familiar with the optimization toolbox but will start reading up on it. The error says:
"Conversion to optim.problemdef.OptimizationExpression from logical is not possible."
Any suggestions on how to avoid this error? I am running 2018b but can upgrade to a different version if necessary. Thanks.
Ah yes, I was using a newer version. You can fix this error by replacing (A==0) with double(A==0). You may also need to replace sum(..., 'all') expressions with sum(sum(...)).

Sign in to comment.