Shortest path through node group sets

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?

Answer 1

[Christine Tobler]

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.

[Skylar Cox]

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.

[Christine Tobler]

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

[Skylar Cox]

That fixed it. Thanks again. Much appreciated!

Answer 2

[Walter Roberson]

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.

[Skylar Cox]

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.

[Walter Roberson]

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.

Answer 3

[Thiago Henrique Gomes Lobato]

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

[Skylar Cox]

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.