Find shortest path with constraints on edges' weight

3 次查看（过去 30 天）
Federico
Federico 2022-12-28
评论： Federico 2022-12-28
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 个评论
显示 1更早的评论
John D'Errico
John D'Errico 2022-12-28
编辑：John D'Errico 2022-12-28
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 2022-12-28
@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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品


版本

R2022b

Community Treasure Hunt

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

Start Hunting!

Translated by