Shortest path through node group sets

4 vues (au cours des 30 derniers jours)
Skylar Cox
Skylar Cox le 9 Nov 2019
Commenté : Skylar Cox le 13 Nov 2019
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?

Réponse acceptée

Christine Tobler
Christine Tobler le 11 Nov 2019
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.
  3 commentaires
Christine Tobler
Christine Tobler le 12 Nov 2019
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
Skylar Cox le 13 Nov 2019
That fixed it. Thanks again. Much appreciated!

Connectez-vous pour commenter.

Plus de réponses (2)

Walter Roberson
Walter Roberson le 9 Nov 2019
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 commentaires
Skylar Cox
Skylar Cox le 9 Nov 2019
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
Walter Roberson le 11 Nov 2019
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.

Connectez-vous pour commenter.


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
  1 commentaire
Skylar Cox
Skylar Cox le 10 Nov 2019
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.

Connectez-vous pour commenter.

Catégories

En savoir plus sur Graph and Network Algorithms dans Help Center et File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by