Trouver tous les chemins Les plus courts entre deux nœuds dans un graphe non pondéré non orienté
J'ai besoin d'aide pour trouver tous les chemins Les plus courts entre deux nœuds dans un graphe non pondéré non orienté.
Je suis capable de trouver L'un des chemins Les plus courts en utilisant BFS, mais jusqu'à présent je suis perdu quant à la façon dont je pourrais trouver et imprimer tous.
Une idée de l'algorithme / pseudocode que je pourrais utiliser?
8 réponses
En guise de mise en garde, rappelez-vous qu'il peut y avoir de façon exponentielle de nombreux chemins Les plus courts entre deux nœuds dans un graphique. Tout algorithme pour cela prendra potentiellement du temps exponentiel.
Cela dit, il existe une modification relativement simple DE BFS que vous pouvez utiliser comme étape de prétraitement pour accélérer la génération de tous les chemins possibles. Rappelez-vous que lorsque BFS s'exécute, il se déroule vers L'extérieur en "couches", obtenant un seul chemin le plus court vers tous les nœuds à la distance 0, puis à la distance 1, puis à la distance 2, etc. L'idée motivante derrière BFS est que tout nœud à la distance k + 1 du nœud de départ doit être connecté par un bord à un nœud à la distance k du nœud de départ. BFS découvre ce nœud à la distance k + 1 en trouvant un chemin de longueur k à un nœud à la distance k, puis en l'étendant par un bord.
Si votre objectif est de trouver tous les chemins Les plus courts, alors vous pouvez modifier BFS en étendant chaque chemin à un nœud à la distance k à tous les nœuds à la distance k + 1 qu'ils connecter, plutôt que de choisir un seul bord. Pour ce faire, modifiez BFS de la manière suivante: chaque fois que vous traitez un edge en ajoutant son point de terminaison dans la file d'attente de traitement, ne marquez pas immédiatement ce nœud comme étant terminé. Au lieu de cela, insérez ce nœud dans la file d'attente annotée avec quel bord vous avez suivi pour y accéder. Cela vous permettra potentiellement d'insérer le même nœud dans la file d'attente plusieurs fois s'il y a plusieurs nœuds qui y sont liés. Lorsque vous supprimez un nœud de la file d'attente, vous le marquez comme étant fait et ne l'insérez plus jamais dans la file d'attente. De même, plutôt que de stocker un pointeur parent unique, vous stockerez plusieurs pointeurs parents, un pour chaque nœud lié à ce nœud.
Si vous faites ce BFS modifié, vous vous retrouverez avec un DAG où chaque nœud sera soit le nœud de départ et n'aura pas d'arêtes sortantes, soit sera à distance k + 1 du nœud de départ et aura un pointeur sur chaque nœud de distance k auquel il est connecté. De là, vous pouvez reconstruire tous les chemins Les plus courts d'un nœud au nœud de départ en répertoriant tous les chemins possibles de votre nœud de choix vers le nœud de départ dans le DAG. Cela peut être fait récursivement:
- Il n'y a qu'un seul chemin entre le nœud de départ et lui-même, à savoir le chemin vide.
- pour tout autre nœud, les chemins peuvent être trouvés en suivant chaque bord sortant, puis en étendant récursivement ces chemins pour générer un chemin vers le nœud de départ.
J'espère que cela aide!
@templatetypedef est correct, mais il a oublié de mentionner la vérification de la distance qui doit être effectuée avant d'ajouter des liens parents au nœud. Cela signifie que se garde la distance de la source dans chacun des nœuds et incrémente d'un la distance pour les enfants. Nous devons ignorer cet incrément et l'addition des parents dans le cas où l'enfant a déjà été visité et a la distance inférieure.
public void addParent(Node n) {
// forbidding the parent it its level is equal to ours
if (n.level == level) {
return;
}
parents.add(n);
level = n.level + 1;
}
L'implémentation java complète peut être trouvée par ce qui suit lien.
J'ai rencontré le problème similaire en résolvant ce https://oj.leetcode.com/problems/word-ladder-ii/
La façon dont j'ai essayé de traiter est d'abord de trouver la distance la plus courte en utilisant BFS, disons que la distance la plus courte est D. maintenant, appliquez DFS et dans l'appel récursif DFS ne dépassez pas le niveau récursif D.
Cependant, cela pourrait finir par explorer tous les chemins comme mentionné par @templatetypedef.
Tout d'abord, recherchez la distance de départ de tous les nœuds à l'aide de la recherche en largeur.
(s'il y a beaucoup de nœuds, vous pouvez utiliser un* et arrêter lorsque le haut de la file d'attente a distance-to-start > distance-to-start(end-node). Cela vous donnera tous les nœuds qui appartiennent à un chemin le plus court)
Ensuite, il suffit de revenir en arrière à partir du nœud final. Chaque fois qu'un nœud est connecté à deux (ou plus) nœuds avec une distance de démarrage inférieure, vous vous divisez en deux (ou plus) chemins.
Templatetypedef votre réponse était très bonne, Merci beaucoup pour celle-ci(!!), mais il a manqué un point:
Si vous avez un graphique comme ceci:
A-B-C-E-F | | D------
Maintenant imaginons que je veux ce chemin:
A -> E.
Il va se développer comme ceci:
A-> B -> D-> C -> F -> E.
Le problème est, que vous aurez F comme parent de E, mais
A->B->D->F-Eest plus long que
A->B->C->E.vous devrez prendre de suivre les distances des parents que vous ajoutez si heureusement.
Étape 1: traverser le graphique de la source par BFS et attribuer à chaque nœud la distance minimale de la source
Étape 2: la distance assignée au nœud cible est la longueur la plus courte
Étape 3: à partir de la source, effectuez une recherche DFS le long de tous les chemins où la distance minimale est augmentée un par un jusqu'à ce que le nœud cible soit atteint ou que la longueur la plus courte soit atteinte. Imprimez le chemin chaque fois que le nœud cible est atteint.
BFS s'arrête lorsque vous trouvez ce que vous voulez.
Vous devez modifier l'algorithme pour qu'il continue son exécution lorsque le premier chemin est trouvé. (supprimez l'instruction return et enregistrez le chemin d'une manière ou d'une autre.
Vous pouvez terminer l'exécution après avoir vérifié le dernier nœud du niveau qui a les nœuds de fin des chemins Les plus courts. (Tous les nœuds de fin des chemins Les plus courts sont au même niveau)
En outre, il algorithme connu qui trouvent tous les plus courts chemins:
De Floyd–Warshall algorithme (il a pseudocode)
Que diriez-vous de ceci: je l'ai trouvé sur Internet