# Bellman-Ford - is number of interations greater than diameter?

Diameter of a connected, undirected graph is the smallest natural number d, so that between any two vertices of the graph exist path of length at most d.

Prove or disprove: in Bellman-Ford is the number of iterations always equal or lower than d.

I'm trying to solve this issue. What I tried was sketching a lot of graphs, however I have failed to find a single graph where the number of iterations would be higher than the diameter.

The only graph where the number of iterations wouldn't be <= than diameter would be a graph with negative edges, however I found out that in undirected graph there can't be any negative edges, otherwhere there would be a negative cycle.

So, AFAIK the statement is correct. However, how would I prove such a statement? I don't even know how to start. Thanks for any help

• What is the length of a path when you define diameter? Is it the sum of the weights of the edges on the path, or the number of edges on the path? – xskxzr May 18 '19 at 13:05
• @xskxzr It's path, so it's the sum of the weights of the edges on the path. – james F. May 18 '19 at 13:52
• What if the weights are very small so that $d=1$? – xskxzr May 18 '19 at 13:54
• @xskxzr If the smallest path between any two vertices is 1, then d=1 – james F. May 18 '19 at 15:32
• Given the context of this question (and that it is about Bellman Ford), I would imagine the diameter its referring to is the number of edges on the longest shortest path. Consider a linked list of 5 nodes where each edge has weight 0.5 (nothing says this can't be the case). Then the diameter according to your definition is 2. However, Bellman-Ford will run 4 iterations in worst case. I would double check how your instructor is defining diameter because I doubt it is sum of edge weights in this context. The distinction to be concerned about is path length vs. path weight. – ryan May 18 '19 at 16:31

In the Bellman–Ford algorithm, after $$t$$ iterations the array contains, for any two nodes, the minimal walk of length at most $$t$$ connecting them. Assuming your graph doesn't have negative weights, the shortest walk between any two vertices will be a path, and so its length would be at most the diameter. Therefore there is no need to run the algorithm beyond $$d$$ iterations.
• There is a subtle nuance, that there is no need to run the algorithm beyond $d$ iterations. However, the prototypical form of the algorithm is to naively run $|V| - 1$ iterations, so it ultimately depends on implementation as to whether or not it runs at most $d$ iterations. – ryan May 20 '19 at 18:46