Plus court chemin avec des itinéraires interdits

[jules]

Bonjour à tous,

Je cherche à obtenir le plus court chemin dans un graphe représentant un réseau ferroviaire.
J'utilisais jusqu'à présent Dijkstra mais j'ai une contrainte que je n'arrive pas à implémenter. Pour certaines bifurcations du réseau (en Y, avec par exemple A - Y - B ; A - Y - C ; B - Y - C), je n'ai pas l'autorisation d'aller de B à C. J'ai ainsi un ensemble de chemins interdits du type (nœud 1 - nœud 2 - nœud 3).

Puis je faire cela avec un Dijkstra modifié? Ou dois je changer d'algorithme?

Merci d'avance!
-----

[umfred]

je n'y connais pas grand chose, mais si B-Y-C est interdit, pourquoi il est présent ?

[Ikhar84]

J'ai peut-être mal compris, en vitesse là entre deux portes...

Pourquoi ne pas supprimer les « arcs » entre les nœuds, quand c'est interdit ?
Pourquoi ne pas mettre des poids abusés sur ces arcs pour alourdir le chemin ?

Est-ce que ces interdictions sont conditionnelles ?

Edit très rapide :
Ajouter un flag de type booléen pour autoriser ou non la branche interdite/autorisée du chemin ?

[Paraboloide_Hyperbolique]

Bonjour,

Si le graphe est mise à jour dynamiquement, durant la recherche du plus court chemin entre deux sommets, il y a la publication suivante qui traite du problème avec un "Dijkstra dynamique".

https://www.researchgate.net/publica...Priority_Queue

[A voir en vidéo sur Futura]

[pm42]

je n'y connais pas grand chose, mais si B-Y-C est interdit, pourquoi il est présent ?

Je dirais que B-Y est autorisé, Y-C aussi quand l'origine n'est pas B. Donc c'est effectivement B-Y-C.
On doit pouvoir construire un graphe équivalent mais suivant le nombre de noeuds, chemins et interdictions, il y a un risque d'explosion combinatoire.

[vgondr98]

Il faut peut-être prend en considération le sens du train ? Si j'ai bien compris quand le train arrive de B à Y, l'arrière du train pointe vers C ?

[jules]

Bonsoir à tous,

Merci de vos réponses.

Si je reprécise mon exemple:
- on a un arc de Y à A, de Y à B, de Y à C.
- mais on a l'interdiction d'aller de B à C via Y

L'idée simple de modifier le graphe en supprimant les 3 arcs YA, YB, YC et en remplaçant par un arc AYB et AYC ne marche pas, car on ne peut pas faire non plus le parcours de B à C en passant par A (ce qui reviendrait à revenir sur ses pas dans le graphe original en faisant BY, YA, AY, YC).

J'aime l'idée de modifier le graphe, mais je vois mal comment faire!

Merci de vos lumières!

[umfred]

En gros, il faut exclure toute combinaison comprenant B, Y et C ?

[pm42]

L'idée simple de modifier le graphe en supprimant les 3 arcs YA, YB, YC et en remplaçant par un arc AYB et AYC ne marche pas, car on ne peut pas faire non plus le parcours de B à C en passant par A (ce qui reviendrait à revenir sur ses pas dans le graphe original en faisant BY, YA, AY, YC).

J'aime l'idée de modifier le graphe, mais je vois mal comment faire!

Tu as essayé en créant un Y' ? B ne va plus vers Y mais vers un Y'. Y' a les mêmes chemins que Y sauf celui qui va en C.
Donc AYB et AYC marchent toujours puisque Y existe toujours. Mais BY'C n'existe plus et juste lui.

[jules]

Merci de ta réponse.

Il faut pouvoir intégrer une liste d'itinéraires interdits du type noeud1 - noeud2 - noeud3 (avec éventuellement noeud3 = noeud1)

Je donne un exemple dans le graphe suivant (non orienté).

Supposons que la liste des itinéraires interdits soit:

- DEC
- EFE

Alors l'itinéraire le plus court entre D et C devient D - A - B - C = 30 km

[Paraboloide_Hyperbolique]

Il faudrait peut-être alors considérer un graphe constitué de "half-edges" (demi-arêtes), ce qui permet d'ajouter une notion de "sens interdit" en supprimant la demi-arête correspondante ?

https://en.wikipedia.org/wiki/Doubly...cted_edge_list

[pm42]

Il faudrait peut-être alors considérer un graphe constitué de "half-edges" (demi-arêtes), ce qui permet d'ajouter une notion de "sens interdit" en supprimant la demi-arête correspondante ?

C'est la solution que le primo-posteur a envisagé dans le message 7 mais elle ne marche pas pour les raisons qu'il a indiqué.

Ce qui marche, c'est ce que j'ai expliqué dans le message 9 : si en venant de B vers Y, on n'a pas les mêmes chemins qu'en venant de A vers Y, alors on crée un Y', on dit que B a un chemin vers Y' au lieu de Y, Y' n'a que les chemins autorisés en venant de B et on ne touche à rien d'autre.
Il faut raffiner un peu si l'orientation des chemins doit être prise en compte mais le principe s'applique.

https://en.wikipedia.org/wiki/Doubly...cted_edge_list

Cela n'a rien à voir avec le sujet : c'est juste une structure de donnée pour représenter efficacement certains graphes.

[Paraboloide_Hyperbolique]

Effectivement, cela ne peut pas fonctionner...

[MissJenny]

annulé - annulé