Comme vous le saviez  que dans l’algorithme de dijkstra les couts entre les sommets sont tous positives par contre l’algorithme bellman ford les couts peuvent étre négative.

Algorithme bellman fortd

Bellmanford (G, C, s)

D[s]ß 0;

Pour chaque vS sauf {s} faire

       D[v]ß

Fin pour   

Pour i ß 1 à |S| -1 faire

                          Pour chaque arc (U, v)  faire

                               Si d(v)>d(U)+c(U, v) alors d(v) ß d(U)+C(U, v)

                               Fin si

                          Fin pour

Fin pour

Pour chaque arc (U, v)  A faire

           Si d(v)>d(U) + C(U, v) alors écrire (« « existe un chemin négative ») ;

Sinon retourner d[v]