Trouver le plus court chemin dans un graphe dont les visites de certains noeuds

J'ai un graphe non-dirigé, avec environ 100 nœuds et environ 200 bords. Un nœud est étiqueté "start", on est "fin", et il y a environ une douzaine de étiquetés "mustpass'.

J'ai besoin de trouver le chemin le plus court à travers ce graphique qui commence à "démarrer", se termine à la fin, et passe à travers tous les mustpass "nœuds" (dans n'importe quel ordre).

( http://3e.org/local/maize-graph.png /http://3e.org/local/maize-graph.dot.txt est le graphe en question - il s'agit d'un labyrinthe de maïs à Lancaster, PA)

InformationsquelleAutor dmd | 2008-10-21