1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Sophie Roseinsta Mar 24 at 17:06
  • $\begingroup$ But I understood your explaination. Thank you very much. $\endgroup$ – Sophie Roseinsta Mar 24 at 17:08
  • $\begingroup$ Thanks for the comment, I have improved it now! $\endgroup$ – Pål GD Mar 24 at 17:33
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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