Find shortest path with constraints on edges' weight
3 views (last 30 days)
Show older comments
I would like to solve the following problem. Given a graph G and a set of weights w for the edges in G, I would like to find the shortest path between two nodes a and b for which no edge has w greater than a given threshold (let's say 10).
The shortestpath function does not work in this case. There is no way of setting constraints as far as I understand and, given that a and b are directly connected with a weight of 90 and no other path has a cumulative weight of less than 90, the shortest path returned is directly a to b. Which is, unfortunately, not what I want.
What I did was to compute all possible paths between a and b using allpaths and then looking for those paths that respected the aforementioned constraints. The shortest one between those was my chosen path.
Unfortunately, when G becomes big and with lots of connections this strategy fails because I run out of memory.
Is there a way to obtain what I want without using allpaths?
3 Comments
John D'Errico
on 28 Dec 2022
Edited: John D'Errico
on 28 Dec 2022
Nothing stops you from removing the unwanted connections in a graph. So have TWO versions of the graph. One (call it G1) that has the unwanted connections. The second (G2) has them removed.
Compute the shortest path using G2. If the path exceeds the imposed limit or no path is found at all, then discard that result, and then accept the result using G1.
Answers (0)
See Also
Categories
Find more on Graph and Network Algorithms in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!