2
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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? $\endgroup$
    – xskxzr
    Commented May 18, 2019 at 13:05
  • $\begingroup$ @xskxzr It's path, so it's the sum of the weights of the edges on the path. $\endgroup$
    – james F.
    Commented May 18, 2019 at 13:52
  • $\begingroup$ What if the weights are very small so that $d=1$? $\endgroup$
    – xskxzr
    Commented May 18, 2019 at 13:54
  • $\begingroup$ @xskxzr If the smallest path between any two vertices is 1, then d=1 $\endgroup$
    – james F.
    Commented May 18, 2019 at 15:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – ryan
    Commented May 18, 2019 at 16:31

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – ryan
    Commented May 20, 2019 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.