Effacer les filtres
Effacer les filtres

Find shortest path with constraints on edges' weight

3 vues (au cours des 30 derniers jours)
Federico
Federico le 28 Déc 2022
Commenté : Federico le 28 Déc 2022
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 commentaires
John D'Errico
John D'Errico le 28 Déc 2022
Modifié(e) : John D'Errico le 28 Déc 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 le 28 Déc 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.

Connectez-vous pour commenter.

Réponses (0)

Catégories

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

Produits


Version

R2022b

Community Treasure Hunt

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

Start Hunting!

Translated by