algorithmAlgorithme Bellman – Ford


Remarques

Étant donné un graphe orienté G , nous voulons souvent trouver la distance la plus courte d'un nœud A donné au reste des nœuds du graphe. L' algorithme de Dijkstra est l'algorithme le plus connu pour trouver le chemin le plus court, mais il ne fonctionne que si les poids d'arête du graphique donné ne sont pas négatifs. Bellman-Ford vise cependant à trouver le chemin le plus court à partir d'un nœud donné (s'il en existe un), même si certains des poids sont négatifs. Notez que la distance la plus courte peut ne pas exister si un cycle négatif est présent dans le graphique (auquel cas nous pouvons contourner le cycle pour obtenir une distance totale infiniment petite). Bellman-Ford nous permet en outre de déterminer la présence d’un tel cycle.

La complexité totale de l'algorithme est O(V*E) , où V - est le nombre de sommets et le nombre E d'arêtes

Algorithme Bellman – Ford Exemples Liés