Algorithme de Bellman et Dijkstra

Bonjour à tous. Je voudrais modifier l’algorithme de bellman et l’algorithme de Dijkstra pour pouvoir calculer le plus long chemin d’un point à tous les autres. Mais quand je remplace min par max je n’obtient pas la réponse. Pouvez vous m’aidez Merci d’avance.

Salut,

Montre-nous ce que tu as fait. Sans ça, c’est difficile de t’aider. De plus, dans la plupart des cas, le plus long chemin est de longueur infinie. Si le sommet de départ de ton graphe a au moins deux voisins et que le graphe n’est pas orienté, la longueur du plus long chemin est de ce point à n’importe quel point est infinie. Donc il faudrait rajouter une autre contrainte (peut-être interdire de passer deux fois par le même point).

Le plus long chemin est infini s’il y a un cycle de poids positif, tout comme le plus court chemin est infini s’il y a un cycle de poids négatif. « Dans la plupart des cas » ne veut pas dire grand chose ici.

Pour répondre à la question de départ, le plus long chemin dans un graphe est le même, s’il existe, que le plus court chemin dans le même graphe avec les poids des arêtes qui deviennent négatifs. L’algorithme est donc quasiment identique, mais il faut seulement faire attention à mettre les « max » et peut-être des soustractions au lieu d’additions aux bons endroits. C’est typiquement quelque chose sur lequel il faut se poser calmement quelques instants plutôt qu’essayer au hasard des modifications jusqu’à ce que ça marche.

Le plus long chemin est infini s’il y a un cycle de poids positif, tout comme le plus court chemin est infini s’il y a un cycle de poids négatif. « Dans la plupart des cas » ne veut pas dire grand chose ici.

Ouep. J’aurais dû préciser.

OK merci

J’ai déjà essayé avec les longueurs négatives. Mais le résultat que j’ai trouver n’est pas juste.

Essaye mieux.

Ok