On dit que DFS ne peut pas être utilisé pour trouver le chemin le plus court dans le graphe non pondéré. J'ai lu plusieurs articles et blogs mais je ne suis pas satisfait car une petite modification dans DFS peut le rendre possible.
Je pense que si nous utilisons le DFS modifié de cette manière, nous pouvons trouver les distances les plus courtes depuis la source.
- Initialisez un tableau de distances à partir de la racine avec l'infini et la distance de la racine à elle-même à 0.
- En parcourant, nous gardons une trace de non. d'arêtes. En avançant, incrément no. d'arêtes et tandis que la piste arrière décrémente pas. d'arêtes. Et à chaque fois vérifier si (dist (v)> dist (u) + 1) alors dist (v) = dist (u) + 1.
De cette façon, nous pouvons trouver les distances les plus courtes depuis la racine en utilisant DFS. Et de cette façon, nous pouvons le trouver dans O (V + E) au lieu de O (ElogV) de Dijkstra.
Si je me trompe à un moment donné. Dites-moi s'il vous plaît.
3 Réponses :
La façon dont la recherche en profondeur d'abord sur les graphiques est définie, elle ne visite chaque nœud qu'une seule fois. Lorsqu'il rencontre un nœud qui a déjà été visité, il revient en arrière.
Supposons donc que vous ayez un triangle aux nœuds A, B, C et que vous vouliez trouver le chemin le plus court de A à B. Une possibilité de traversée DFS est A -> C -> B et vous avez terminé. Ce n'est cependant pas le chemin le plus court.
Vous êtes Rite d'une manière. Que dire de DFS modifié comme je l'ai expliqué?
@coderAJ oui, vous pouvez adapter DFS pour prendre en charge la recherche de chemin le plus court, mais ce n'est plus DFS. Il manque une partie importante à votre adaptation: quand revenir en arrière. Je suppose que vous voulez revenir en arrière si dist (v)
Oui, si l'algorithme DFS est modifié comme vous l'avez mentionné, il peut être utilisé pour trouver les chemins les plus courts à partir d'une racine dans un graphe non pondéré. Le problème est qu'en modifiant l'algorithme, vous avez fondamentalement changé ce qu'il est.
Il peut sembler que j'exagère car le changement semble mineur en apparence mais il le change plus que vous ne le pensez.
Considérons un graphe avec n nœuds numérotés de 1 à n . Soit une arête entre chaque k et k + 1 . Aussi, laissez 1 être connecté à chaque nœud.
Puisque DFS peut choisir des voisins adjacents dans n'importe quel ordre, supposons également que cet algorithme les sélectionne toujours dans un ordre numérique croissant.
Maintenant, essayez d'exécuter l'algorithme dans votre tête ou votre ordinateur avec la racine 1 .
Premièrement, l'algorithme atteindra n en n-1 étapes en utilisant des arêtes entre 1-2 , 2-3 et bientôt. Puis après retour en arrière, l'algorithme passe au deuxième voisin de 1 , à savoir 3 . Cette fois, il y aura n-2 étapes.
Le même processus se répétera jusqu'à ce que l'algorithme voie enfin 1-n .
L'algorithme aura besoin d'étapes O (n ^ 2) plutôt que O (n) pour terminer. N'oubliez pas que V = n & E = 2 * n - 3 . Ce n'est donc pas O (V + E).
En fait, l'algorithme que vous avez décrit se terminera toujours par O (V ^ 2) sur les graphes non pondérés. Je laisserai la preuve de cette réclamation comme un exercice pour le lecteur.
O (V ^ 2) n'est pas si mal. Surtout si un graphique est dense. Mais comme BFS fournit déjà une réponse en O (V + E), personne n'utilise DFS pour le calcul de la distance la plus courte.
pouvez-vous s'il vous plaît donner quelques conseils sur la façon de prouver que cet algorithme fonctionne en temps O (V ^ 2)?, pour autant que je sache, nous ne faisons que revenir en arrière si dist (v)
Dans cette question , je pense que la même chose est évoquée about (pour les graphes pondérés cependant), en voyant le pseudo-code il est évident que pour chaque appel à dfs (u) nous explorerons toutes les arêtes partant de "u" si la condition dist (u) +1
Dans un graphique non pondéré, vous pouvez utiliser une recherche en largeur d'abord (pas DFS) pour trouver les chemins les plus courts en temps O (E).
En fait, si toutes les arêtes ont le même poids, alors l'algorithme et la largeur de Dijkstra -first recherche est à peu près équivalente - reductionKey () n'est jamais appelée, et la file d'attente prioritaire peut être remplacée par une file d'attente FIFO, puisque les sommets nouvellement ajoutés n'ont jamais un poids plus petit que ceux précédemment ajoutés.
Votre la modification de DFS ne fonctionne pas, car une fois que vous visitez un sommet, vous n'examinerez plus ses enfants, même si son poids change. Vous obtiendrez la mauvaise réponse pour ce graphique si vous suivez S-> A avant S-> B
S---->A---->C---->D---->E---->T \ / ------->B-----/
Voir ceci
J'ai lu ceci. Mais un peu de DFS modifié peut le rendre possible. Trouvez-vous une erreur dans ma méthode?