Skip to main content
fixed def of m_v
Source Link
John Kemeny
  • 17.1k
  • 3
  • 43
  • 67

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. Let us calledges; 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 endingstarting 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.

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. Let us call this number $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 ending 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.

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.

Source Link
John Kemeny
  • 17.1k
  • 3
  • 43
  • 67

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. Let us call this number $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 ending 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.