# Why do we need to run the bellman-ford algorithm for n-1 times?

I'm a little confused about the concept of the Bellman-Ford(BF) algorithm to compute the shortest path in a general graph with negative weights knowing that there are no negative cycles present. I understand why Dikjstra doesn't work for a graph with negative weights. So in the Bellman-Ford algorithm we decide to update all nodes and their neighbors even though they might be visited before. My confusion can be summarized in a couple of questions:

1. Why running the BF algorithm once won't make sure that all nodes' distances have the minimum distance from the source?

2. Why do we have to run BF for N-1 (N: number of nodes) times to make sure all the nodes have the minimum distance from the source? Is it sort of because there are negative weights? How negative weights complicate things?

• "Why do we have to run BF for N-1 times" -- we don't. You seem to have misunderstood something. – Raphael Dec 10 '15 at 9:20
• Please refer to my answer here, with example, and hopefully it's easier for you fellows to understand: stackoverflow.com/questions/49263065/… – Isaac_Zhu Sep 29 '19 at 9:48

Answering your first question is simple. Try out a few graphs and see for yourself why it doesn't work. As to your second question, $n-1$ is the maximal length of a shortest path in the graph. After $k$ iterations of the Bellman–Ford algorithm, you know the minimum distance between any two vertices, when restricted to paths of length at most $k$. This is why you need $n-1$ iterations. Negative weights have absolutely nothing to do with it.
The longest possible shortest path from source s to destination $$v_k$$ can have $$|V|-1$$ "stops". According to Lemma 24.15 Path-relaxation property in CLRS, after each "relaxation" step, you get $$v_i=\delta(s, v_i)$$ and this value remains unchanged ever since. So after $$|V|-1$$ times we must finish finding all results for a single-source shortest path problem. You make easily find a counterexample to say why loop for fewer than$$|V|-1$$ will fail to find all shortest paths.