필터 지우기
필터 지우기

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
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 CenterFile 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