# Problem to understand a Bellman Ford algorithm exercise

I am trying to understand the following exercise from Introduction to algorithm (3rd edtion).

Exercise 24.1-3 (page 654)

Given a weighted, directed graph $$G=(V, E)$$ with no negative-weight cycles, let $$m$$ be the maximum over all vertices $$v \in V$$ of the minimum number of edges in a shortest path from source $$s$$ to $$v$$. (Here, the shortest path is by weight, not the number of edges.) Suggest a simple change to the Bellman-Ford algorithm that allows it to terminate in $$m + 1$$ passes, even if $$m$$ is not known in advances.

So what is $$m$$ exactly? I am really have the trouble to understand the first sentence.

The only way to understand it is to break it down.

Given a weighted, directed graph $$G=(V, E)$$ with no negative-weight cycles, let $$m$$ be the maximum over all vertices $$v \in V$$ of the minimum number of edges in a shortest path from source $$s$$ to $$v$$. (Here, the shortest path is by weight, not the number of edges.)

Okay, so $$s$$ is fixed, and let us suppose you have a vertex $$v$$.

Now we look at all the cheapest paths from $$s$$ to $$v$$ and we take the path that has the fewest edges; this number of edges we refer to as $$m_v$$.

If we repeat this for every vertex $$v \in V$$, then we get one $$m_v$$ for each $$v$$. The value $$m$$ is the maximum of all $$m_v$$s, or $$\max_{v \neq s}m_v$$.

Or in other words, over all cheapest paths starting in $$s$$, let us look at the vertex with the longest shortest. It has length $$m$$.

It is confusing because we want the longest shortest over all the cheapest.

• Can you edit "Let us call this number $m_v$" to something more specific? I suppose you meant $m_v$ is the number of edges of the path? Mar 24, 2021 at 17:06
• But I understood your explaination. Thank you very much. Mar 24, 2021 at 17:08
• Thanks for the comment, I have improved it now! Mar 24, 2021 at 17:33

Suppose our graph be line graph, or path graph, in such a graph $$m$$ equal to $$v-1$$ so we can say over algorithm run $$m$$ times and in iteration $$m+1$$ no distance of any node updated, so it's sufficient to continue until a iteration that no $$d[v]$$ updated.

note that in this worst case example, $$\max\min_{m\in V}\ell$$ have $$V-1$$ edges