Parcours de Graphes

Bonjour,

Dans le cadre de stage de fin d'étude, je dois manipuler des graphes (orienté ou non orienté) et je cherche des méthodes de parcours.

Je cherche des méthodes heuristiques de parcours qui seraient capables de me donner un chemin optimal ou le chemin le plus cours entre deux points. Sans pouvoir repasser par un point.

Actuellement je test l'algorithme de colonies de fourmis. Qui sur le papier semble pouvoir répondre à ma problématique.

Mais j'aurai aimé avoir d'autres pistes et d'autres algorithmes à tester pour évaluer leurs résultats et leurs robustesses.

Si vous avez des idées je suis preneur..

Merci.

Bien cordialement,
Guilhem

Sur des petites graphes, tu peux utiliser un algorithme trivial qui vérifie tous les chemins possibles et ne retient que le meilleur. Tu es ainsi assuré d'avoir le meilleur chemin et tu peux le comparer avec le résultat de l'algorithme fourmi.
Ensuite, tu extrapoles en prétendant que l'algo fourmi trouve l'un des meilleurs chemin sur un petit graphe, donc il fera de même sur un graphe gigantesque.