Pourquoi DFS ne peut-il pas être utilisé pour trouver les chemins les plus courts dans les graphiques non pondérés?

Je comprends que l'utilisation de DFS "tel quel" ne trouvera pas le chemin le plus court dans un graphique non pondéré.

Mais pourquoi modifier DFS pour lui permettre de trouver les chemins les plus courts dans les graphiques non pondérés est-il une perspective désespérée? Tous les textes sur le sujet indiquent simplement que cela ne peut pas être fait. Je ne suis pas convaincu (sans l'avoir essayé moi-même).

Connaissez-vous des modifications qui permettront à DFS de trouver les chemins les plus courts dans les graphiques non pondérés? Sinon, qu'est-ce qui rend l'algorithme si difficile?

Le seul élément de la recherche en profondeur que vous modifiez est l'ordre dans lequel les enfants sont examinés. La version normale se déroule dans un ordre arbitraire, c'est-à-dire dans l'ordre dans lequel les enfants sont stockés.

La seule alternative possible (vers les chemins les plus courts) que je peux trouver est une approche gourmande, qui regarde les enfants par ordre de distance par rapport au nœud actuel (de petit à grand). Il est facile de construire un contre-exemple pour cette règle:

^{[ source ]}

Maintenant, ce n'est pas une preuve qu'il n'existe pas de stratégie de choix du prochain enfant à étudier qui permettra à DFS de trouver les chemins les plus courts.

Cependant, peu importe la règle¹, vous pouvez construire des graphiques qui font que DFS s'engage à faire un long détour au tout premier nœud, comme je l'ai fait pour la règle gourmande. Attribuez des arêtes et telle sorte que la règle choisisse de visiter première, et affectez un poids supérieur à celui de . Par conséquent, il est plausible que DFS ne puisse jamais trouver les chemins les plus courts (dans les graphiques généraux).( s , a ) a ( a , b ) ( s , t $(s,t)$$(s,a)$$a$$(a,b)$$(s,t)$

Notez que puisque vous pouvez exprimer chaque graphique pondéré (entier positif) sous forme de graphique non pondéré - remplacez simplement les arêtes par le coût par une chaîne avec nœuds - les mêmes exemples concernent le DFS sur les graphiques non pondérés. Ici, la situation est encore plus sombre: sans poids, que peut utiliser DFS pour déterminer le prochain enfant à visiter?c - $c$$c-1$

1. Tant que la règle est déterministe. Si ce n'est pas le cas, il ne peut clairement pas toujours trouver les chemins les plus courts.

L'étendue -première-recherche est l'algorithme qui trouvera les chemins les plus courts dans un graphique non pondéré.

Il existe un simple ajustement pour passer de DFS à un algorithme qui trouvera les chemins les plus courts sur un graphique non pondéré. Essentiellement, vous remplacez la pile utilisée par DFS par une file d'attente. Cependant, l'algorithme résultant n'est plus appelé DFS. Au lieu de cela, vous aurez implémenté la recherche en largeur d'abord.

Le paragraphe ci-dessus donne une intuition correcte, mais simplifie un peu trop la situation. Il est facile d'écrire du code pour lequel le simple échange donne une implémentation de la première recherche étendue, mais il est également facile d'écrire du code qui ressemble à première vue à une implémentation correcte mais qui ne l'est pas. Vous pouvez trouver une question connexe cs.SE sur BFS vs DFS ici . Vous pouvez trouver un joli pseudo-code ici.

Vous pouvez!!!

Marquez les nœuds comme visités pendant que vous allez en profondeur et démarquez-vous lorsque vous revenez, tout en revenant lorsque vous trouvez une ou plusieurs autres branches, répétez la même chose.

Enregistrez le coût / chemin pour toutes les recherches possibles où vous avez trouvé le nœud cible, comparez tous ces coûts / chemin et choisissez le plus court.

Le gros problème (et je veux dire GRAND) avec cette approche est que vous visiteriez le même nœud plusieurs fois, ce qui fait de dfs un mauvais choix évident pour l'algorithme de chemin le plus court.

BFS a une belle propriété qui vérifiera tous les bords de la racine et gardera la distance de la racine aux autres nœuds aussi minime que possible, mais dfs saute simplement au premier nœud adjacent et va en profondeur. Vous POUVEZ modifier DFS pour obtenir le chemin le plus court, mais vous ne vous retrouverez que dans un algorithme de complexité temporelle plus élevée ou finirez par faire la même chose que BFS.

IL est possible de trouver le chemin entre deux sommets avec le nombre minimum d'arêtes en utilisant DFS. nous pouvons appliquer une approche de niveau

Vous pouvez

il suffit de parcourir le graphique de manière dfs et de vérifier

if(distance[dest] > distance[source]+cost[source_to_destination]){
    distance[dest] = distance[source] + cost[source_to_destination]);
}

Voici le lien pour une solution complète