Version imprimable
Bonjour,
Je viens de voir l'algorithme de Bellman qui permet de déterminer le chemin le plus court dans un graphe orienté mais comment faire un recherche de chemin le plus cours dans un graphe qui peut posséder des circuits (comme un entrepôt par exemple) ???
D'avance merci de votre aide.
L'algorithme de Bellman fonctionne pour un graphe avec circuit (sauf s'il existe un circuit négatif, cas dans lequel le problème n'a pas de sens).
Tu dois parler de l'algorithme de Bellman simplifié, qui lui ne fonctionne pas sur les graphes avec circuit.
Tu peux donc utiliser l'algo de Bellman, ou l'algorithme de Dijkstra si ton graphe ne comporte que des poids positifs ou nuls.
Quand tu parle de poids tu parle de distance entre 2 points ?
Oui. Si tu traites des distances euclidiennes, je suppose qu'elles sont positives. Tu peux donc utiliser l'algo de Dijkstra.
P.S.: quand j'ai dit "circuit négatif" je voulais dire "circuit de coût négatif".