Problem to understand a Bellman Ford algorithm exercise

Question

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.

Answer 1

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.

Answer 2

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