prob d'algorithme dans matrice

Question

Bonjour, 

Voila je dois &#233;crire un prg en C qui joue avec des matrices bool&#233;ennes.
J'ai d&#233;j&#224; fait la partie addition, multiplication, je suis entrain d'impl&#233;menter l'algo de floyd pour le plus court chemin...

Mais je me demandais si il existait un algo qui pouvais me donner l'existence de chemins entre deux sommets de ma matrice (carr&#233;e et bool&#233;enne) et si possible me donner le plus court.

Si vous connaissiez le nom d'un algo ou peut &#234;tre m&#234;me un petit bout de code pour m'aider ca serait sympa parce que la je commence un peu &#224; patauger.

Merci

BunoCS · Answer

Cherche du c&#244;t&#233; de Dijkstra et/ou de l'algorithme A*...

Je sais, c'est peu, mais se sont des pistes...

Buno
----------------------------------------
L'urgent est fait, l'impossible reste &#224; faire. Pour les miracles, pr&#233;voir un d&#233;lai...

gregorian · Answer

Salut, 

Peux tu m'en dire un peu plus sur l'algo A* j'ai fait une recherche mais ???
Sinon je croyais que Dijkstra ne concernait que la recherche du plus court chemin en g&#233;n&#233;ral. Y a t'il moyen de le faire pour un poin A &#224; un point B ?

Sinon merci pour ta r&#233;ponse rapide

sfkuhvdlkufgs · Answer

pour verifier l'existence d'un chemin, tu part de ton premeier sommet (A), tu regarde la ou tu peut aller (B), et tu fais une recursivit&#233;, en appelant en premier sommet B.
conditions d'arret : 1)si &#224; un moment A=sommet de dest alors c'est bon, si
2) si les sommet ou tu peut all&#233;r on d&#233;ja tous &#233;t&#233;s atteint (pense a faire une liste de sommet atteint)  alors pas de chemin entre A et  ton sommet de dest

Prob d'algorithme dans matrice

3 réponses

Votre réponse

Discussions similaires