Find shortest path with constraints on edges' weight

4 views (last 30 days)
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
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.
Federico
Federico on 28 Dec 2022
@Torsten and @John D'Errico thanks for you answers, they actually make lots of sense.
I've used the "allpaths" approach because I was also interested to ranking the possible paths, but removing the unwanted connections by setting to 'Inf' makes at least possible to find the shortest path.

Sign in to comment.

Answers (0)

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Products


Release

R2022b

Community Treasure Hunt

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

Start Hunting!