Discussion :

[egu07]

Bonjour,

Je dispose d'un graphe non orienté, composé de noeuds et d'arcs pondérés.

Chacun des noeuds est reliés aux autres; c'est à dire que tous les couples possibles font l'objet d'un arc pondéré. Le graphe est donc complet. Tous les chemins sont possibles.

Je souhaite entrer dans mon graphe par un noeud A, en ressortir par un autre B, et trouver le chemin le plus court entre A et B mais passant par l'ensemble des autres noeuds (autres que A et B). Peut être sera t-il necessaire de repasser par un point déjà parcouru, mais attention aux boucles !!

L'algo de Dijkstra ne s'y prète donc pas.
L'algo du voyageur de commerce non plus, car j'ai compris qu'il recherche le chemin le plus court en partant de A et revenant à A en passant par tous les autres points. CE QUI EST DIFFERENT DE MON CAS DE FIGURE.

Savez-vous s'il existe un algo qui fait cela ou bien pouvez-vous me proposer une méthode ???
Pour info, le graphe peut intégrer 100 noeuds, voire plus !!

Merci beaucoup.

[Furikawari]

Si tu ajoutes une arête de poids négatif suffisant entre A et B, tu es certain qu'une résolution par voyageur de commerce prendra cette arête. Il te suffit d'enlever cette arête pour avoir la solution a ton problème.