Quel est l'algorithme/solution le plus simple pour un chemin le plus court d'une seule paire dans un graphe non orienté à pondération réelle ?

Question

Je dois trouver le plus court chemin dans un graphe non orienté dont les nœuds ont une pondération réelle (positive et négative). Ces poids sont comme des ressources que vous pouvez gagner ou perdre en entrant dans le nœud.

Le coût total (somme des ressources) du chemin n'est pas très important, mais il doit être supérieur à 0, et la longueur doit être la plus courte possible.

Par exemple, considérez un graphique comme celui-ci :

A-start node; D-end node

A(+10)--B( 0 )--C(-5 )
     \     |    /
       \   |  /
D(-5 )--E(-5 )--F(+10)

Le chemin le plus court serait A-E-F-E-D

L'algorithme de Dijkstra seul ne fait pas l'affaire, car il ne peut pas gérer les valeurs négatives. J'ai donc réfléchi à quelques solutions :

La première utilise l'algorithme de Dijkstra pour calculer la longueur du plus court chemin entre chaque nœud et le nœud de sortie, sans tenir compte des poids. Cela peut être utilisé comme une sorte de valeur heuristique comme dans A*. Je ne suis pas sûr que cette solution puisse fonctionner, et en plus elle est très coûteuse. J'ai également pensé à mettre en œuvre l'algorithme de Floyd-Warshall, mais je ne sais pas comment.

Une autre solution consistait à calculer le plus court chemin avec l'algorithme de Dijkstra sans tenir compte des poids, et si après avoir calculé la somme des ressources du chemin elle est inférieure à zéro, passer par chaque nœud pour trouver un nœud voisin qui pourrait rapidement augmenter la somme des ressources, et l'ajouter au chemin (plusieurs fois si nécessaire). Cette solution ne fonctionnera pas s'il y a un nœud qui pourrait suffire à augmenter la somme des ressources, mais qui est plus éloigné du plus court chemin calculé.

Par exemple :

A- start node; E- end node
A(+10)--B(-5 )--C(+40)
      \
        D(-5 )--E(-5 )

Pourriez-vous m'aider à résoudre ce problème ?

EDIT : Si, en calculant le chemin le plus court, vous atteignez un point où la somme des ressources est égale à zéro, ce chemin n'est pas valable, car vous ne pouvez pas continuer s'il n'y a plus d'essence.

Answer 1

Edit : Je n'ai pas assez bien lu la question ; le problème est plus avancé qu'un problème ordinaire de plus court chemin à source unique. Je laisse ce message pour le moment, juste pour vous donner un autre algorithme qui pourrait vous être utile.

El algorithme de Bellman-Ford résout le problème du plus court chemin à source unique, même en présence d'arêtes de poids négatif. Cependant, il ne gère pas les cycles (un chemin circulaire dans le graphe dont la somme des poids est négative). Si votre graphe contient des cycles négatifs, vous êtes probablement dans le pétrin, parce que je crois que cela rend le problème NP-complet (parce qu'il correspond à l'équation le problème du plus long chemin simple ).

Answer 2

Cela ne semble pas être une solution élégante, mais étant donné la possibilité de créer des chemins cycliques, je ne vois pas comment l'éviter. Mais je me contenterais de la résoudre de manière itérative. En utilisant le deuxième exemple - Commencez avec un point en A, donnez-lui la valeur de A. Déplacez-vous d'un "tour". Déplacez-vous d'un tour - j'ai maintenant deux points, un en B avec une valeur de 5, et un en D également avec une valeur de 5. Déplacez-vous à nouveau - j'ai maintenant 4 points à suivre. C : 45, A : 15, A : 15, et E : 0. Il se peut que le point en E puisse osciller et devenir valide, donc nous ne pouvons pas encore le jeter. Déplacez et accumulez, etc. La première fois que vous atteignez le nœud final avec une valeur positive, vous avez terminé (bien qu'il puisse y avoir d'autres chemins équivalents qui arrivent dans le même tour).

Évidemment, le problème est que le nombre de points à suivre augmentera assez rapidement, et je suppose que votre graphique réel est beaucoup plus complexe que l'exemple.

Answer 3

Je procéderais de la même manière que ce que Mikeb a suggéré : faire une recherche en largeur sur le graphe des états possibles, c'est-à-dire les paires (position, carburant-gauche).

En utilisant votre exemple de graphique :

• Octogones : En panne de carburant
• Boîtes : Nœuds enfants omis pour des raisons d'espace

La recherche dans ce graphe en premier est garantie pour vous donner le chemin le plus court qui atteint réellement le but. si une telle route existe . Si ce n'est pas le cas, vous devrez abandonner après un certain temps (après x nœuds recherchés, ou peut-être lorsque vous atteindrez un nœud dont le score est supérieur à la valeur absolue de tous les scores négatifs combinés), car le graphique peut contenir des boucles infinies.

Si vous souhaitez également trouver le chemin le moins cher (en termes de carburant), vous devez veiller à ne pas abandonner immédiatement après avoir trouvé le but, car vous pourriez trouver plusieurs chemins de même longueur, mais avec des coûts différents.

Answer 4

Essayez d'ajouter la valeur absolue du poids minimum (dans ce cas 5) à tous les poids. Cela évitera les chemins cicliques négatifs.

Les algorithmes de plus court chemin actuels nécessitent de calculer le plus court chemin pour chaque nœud, car ils vont combiner des solutions sur certains nœuds qui aideront à ajuster le plus court chemin dans d'autres nœuds. Il n'est pas possible de le faire uniquement pour un seul nœud.

Bonne chance