Une question algorithmique concernant les chemins les plus courts et tels

J'ai un très, très grand graphe, et je veux trouver le chemin le plus court d'un sommet à l'autre. Le graphique est dirigé et non pondéré.Une question algorithmique concernant les chemins les plus courts et tels

J'ai envisagé d'utiliser une certaine modification de l'algorithme de Dijkstra, mais j'utilise généralement celle-ci pour les graphes non orientés pondérés. Alors, mon autre pensée était d'utiliser un DFS, puisque je peux traiter tous les poids comme un seul.

Des suggestions? a

EDIT: Ok, je voulais dire BFS, je suis désolé.

Source

2010-07-05 Alex

Combien de nœuds avez-vous et combien d'arêtes? –

Je ne recommande pas DFS: http://xkcd.com/761/ – Bolo

Essayez plutôt un BFS.

(Notez que l'algorithme de Dijkstra fonctionne parfaitement bien pour les graphes non pondérés réalisés - il se trouve que dans le cas non pondéré, le faire est intelligemment essentiellement équivalente à une recherche en largeur.)

Source

2010-07-05 22:02:58

J'ai fusionné le commentaire de ma réponse dans ceci et supprimé le mien; n'hésitez pas à supprimer le commentaire si vous (ne) voulez pas. :-) – ShreevatsaR

Avez-vous essayé d'utiliser A*?

Source

2010-07-05 21:53:59 David

Il n'y a absolument aucun intérêt à utiliser A * ici avec un graphique non-pondéré ... cela ne ferait rien de mieux qu'une recherche de grande taille, et peut-être prendre plus de temps (à moins que vous ne le fassiez correctement, auquel cas * est * une recherche en largeur d'abord). – ShreevatsaR

Je suis d'accord avec ShreevatsaR :) –

Une question algorithmique concernant les chemins les plus courts et tels

Répondre

Questions connexes