Trouver le chemin le plus court en présence de cycles négatifs

Étant donné un graphique cyclique dirigé où le poids de chaque bord peut être négatif, le concept de "chemin le plus court" n'a de sens que s'il n'y a pas de cycles négatifs, et dans ce cas, vous pouvez appliquer l'algorithme Bellman-Ford.

Cependant, je suis intéressé à trouver le chemin le plus court entre deux sommets qui n'implique pas de cycle (c'est-à-dire sous la contrainte que vous ne puissiez pas visiter le même sommet deux fois). Ce problème est-il bien étudié? Peut-on utiliser une variante de l'algorithme Bellman-Ford, et sinon, existe-t-il une autre solution?

Je suis également intéressé par le problème de toutes les paires équivalentes, pour lequel je pourrais sinon appliquer Floyd – Warshall.

Les chemins sans sommets répétés sont appelés chemins simples , vous recherchez donc le chemin simple le plus court dans un graphique avec des cycles négatifs.

Cela peut être réduit du problème du chemin le plus long . S'il y avait un solveur rapide pour votre problème, alors étant donné un graphique avec uniquement des poids de bord positifs, la négation de tous les poids de bord et l'exécution de votre solveur donneraient le chemin le plus long dans le graphique d'origine.

Votre problème est donc NP-Hard.