modification algorithme du plus court chemin, sentiers interdits

Question

Nous sont pourvus d'un graphe G = (V, E), où chaque arête est associée à un certain poids positif (P [i]> 0). On nous demande de trouver le chemin le plus court de A à B, à condition que nous suivons les conditions suivantes:

Nous sommes également donné des chemins interdits, par exemple x. Le but est que le chemin le plus court ne contienne aucun chemin interdit comme sous-chemin. Par exemple: Considérons un graphe G avec 4 sommets et 5 arêtes (1, 2, 1), (2, 1, 1), (1, 4, 5), (1, 3, 1.5), (3, 4, 1). Ici, la 3ème entité dans la parenthèse indique le poids du bord entre 'u' et 'v'. Nous devons trouver le chemin le plus court entre 1 et 4, et la liste des chemins interdits ne contient que le chemin 1-> 3-> 4.

Les chemins de 1 à 4 sont 1 -> 4, 1 -> 2 -> 3 -> 4, 1 -> 3 -> 4.

Sur ce total, seulement 2 sont 1er chemins valides, et parmi eux le chemin le plus court est 1 -> 2 -> 3 -> 4 du poids total en tant que 3,0.

Y at-il un algorithme efficace pour la tâche ci-dessus? Veuillez décrire l'algorithme avec l'analyse de complexité. Je serais très reconnaissant si vous pouviez fournir un code aussi.

Answer 1

Vous pouvez prétraiter le graphique de manière à intégrer les chemins interdits à en-it. Pour chaque chemin interdit, vous dupliquez les vertices qui lui appartiennent et ensuite vous en déposez quelques-uns. Cette duplication aurait une signification particulière: marcher le long d'un bord dupliqué signifierait que vous êtes arrivé à un sommet le long du chemin interdit et que vous ne pouvez pas marcher le long du dernier bord. Si vous marchez le long des bords originaux, alors vous êtes venu quelque part au milieu du chemin interdit, donc cela ne vous affecte pas. Pour y parvenir, vous placez tous les bords entrants dans un chemin dupliqué, excepté le bord et le second sommet du premier sommet. Mais vous laissez tomber ce bord du chemin d'origine.

un Foryou fendu sommets qui font partie à plusieurs en-sommets virtuels chemins interdits et laissent tomber quelques-uns des bords. Supposons que dans le chemin de graphique suivant ABC est interdit:

A-->B-->C 
D->/ 

Ensuite, vous divisez B à BA et BD (en fonction de quel sommet vous venez à B) et déposer BA-> bord C.

A->BA /->C 
D->BD-/ 

Maintenant, vous pouvez utiliser dijkstra classique sur ce graphique prétraité.

Plus exemple complexe, supposons que ABCF est interdit:

G->\ 
A-->B-->C-->F 
D->/ \->E 

Nous dupliquer B et C sommets internes de la route interdite, nous laissons tomber A> bord B et ne laisser que A> B '. Nous laissons également tous les autres bords entrants vers B 'et C' mais nous laissons B '-> E car il s'éloigne de la route interdite. Nous laissons également tomber le bord C '-> F.

/->B'-->C' 
| \------->\ 
|    \ 
| G->\  \ 
A B-->C---->F \ 
D->/ \----------->E