Can we find single-source shortest path in a weighted graph having zero-weighted cycle in it?

257 Views Asked by At

If we have a zero-weighted cycle in a graph , then the zero-weighted cycle won't decrease the overall cost of shortest path , so we can find shortest path in it right ?

Also can we have a zero-weighted cycle in a shortest path from source vertex to all vertices ?

1

There are 1 best solutions below

0
On

Yes we can indeed find a shortest path in a graph with a zero-weighted cycle. Consider the Bellman-Ford algorithm, which finds the shortest path from a source vertex $s$ to every other vertex in a directed weighted graph. You might already be familiar with the algorithm, but let's examine how it operates when there are zero-weighted cycles present.

The algorithm and correctness

Suppose that $G = (V,E,w)$ is a directed graph, where for each edge $(v,u) \in E$, the $w\left((v,u)\right) \in \mathbb{R}$ denotes the weight of the edge. During the course of the algorithm, we associate to each vertex $v \in V$ the current predecessor $p(v)$ on the shortest path from $s$ to $v$, and the distance of that path $d(v)$. The algorithm runs as follows:

  1. In the beginning, we initialize $d(s) := 0$ and otherwise $d(v) := \infty$, for each $v \in V$. We also intialize $p(v) = \mathrm{null}$, for each $v \in V$.

  2. Then we relax the distances, $d(v)$, by repeating the following procedure $|V|-1$ times:

    • For each edge $(v,u) \in E$, if $d(v) + w\left((v,u)\right) < d(u)$, then set $p(u) := v$ and $d(u) := d(v) + w\left((v,u)\right)$.
  3. After going through all the edges $|V|-1$ times, we check if we still can relax some of the distances, i.e. for each edge $(v,u) \in E$, we check if $d(v) + w\left((v,u)\right) < d(u)$.

    • If such an edge is found, then we have found a negative cycle

    • If no such edge is found, we can find the shortest path from $s$ to each vertex $v$ in reverse order by following the chain of predecessors, starting form $v$ and ending up in $s$.

Why this algorithm works can be briefly justified as follows:

  • First of all, if $d(v) < \infty$, for some vertex $v \in V$, then $d(v)$ is the distance of $v$ from $s$ on some actual (not necessarily shortest) path: It clearly holds after phase 1., since $s$ is a distance $0$ from itself. Now if $d(v)$ is a distance of a path from $s$ to $v$, then $d(v) + w\left((v,u)\right)$ is a distance of a path from $s$ to $u$ and the claim follows by induction.

  • Second, we claim that after $i$ iterations of step 2., if there is a path of length $i$ from $s$ to any $u$, then $d(u)$ is the length of the shortest such path of length at most $i$: This again clearly holds after $0$ iterations.

    • Suppose that the claim holds for $i-1$ and suppose that $P$ is a shortest path of length at most $i$ from $s$ to $u$ and let $v$ be the predecessor of $u$ on that path.
    • Then the path $P - (v,u)$ (the $|P|-1$ steps up to $v$) is a shortest path of length at most $i-1$ from $s$ to $v$, since if there was a shorter path $Q$ of length $i-1$, then $Q + (v,u)$ (path Q with (v,u) appended) would have a strictly shorter distance than $P + (v,u) = P$, which is a contradiction.
    • Now by inductive assumption $d(v)$ is the shortest distance on a path of length at most $i-1$ from $s$ to $v$ and thus, if $d(u)$ is not already the length of a shortest path of length at most $i$ from $s$ to $u$, then after setting $d(u) := d(v) + w\left((v,u)\right)$, it will be. The claim follows by induction.
  • If there are no negative weight cycles, there exists a shortest path from $s$ to any vertex $u \in V$ with no cycles, because with no negative cycles, a cycle could only increase the distance of the path (or keep it unaltered). Since every path with no cycles must visit each vertex at most once, the length of such a path is at most $|V|-1$.

  • Now since the relaxation procedure is repeated $|V|-1$ times, after completing step 2., $d(u)$ gives the shortest distance from $s$ to $u$ on a path of length at most $|V|-1$.

    • By the previous bullet point, this means that if there are no negative cycles, the $d(u)$ give the shortest distance from $s$ to each $u \in V$ and it can easily be seen that following the predecessors gives a corresponding path.
    • If the distance can be further improved in step 3., we know that we have a path of length $|V|$ which is strictly shorter than any path of length $|V|-1$, meaning that the path of length $|V|$ must have a negative cycle.

Graphs with zero-weighted cycles

Now what happens when zero-weighted cycles are present? The proof, that after $i$ steps the algorithm produces paths that are the shortest of all paths of length at most $i$, holds also when negative weights are present. So, after completing all iterations of step 2., the algorithm finds the shortest paths of length at most $|V|-1$. We also concluded that if there are no negative weight cycles, these will provide the shortest paths from $s$ to any other vertex $v$. All of this also holds with zero-weighted cycles, since adding a zero-weighted cycle to a path will not make it shorter.

Thus, the algorithm can find a shortest path from a single source vertex to every other vertex even when zero-weighted cycles are present.

The algorithm will in fact produce the paths that don't have a zero-weighted cycle in them. This is due to the fact that if we have a shortest path $P$ with a zero-weighted cycle, we can form a new path $Q$ that has the same weight but is shorter in length, by removing the cycle. Thus, a shortest (with respect to weight) path from $s$ to any $u$, that is also shortest in length, will not have zero-weighted cycles. Now since the algorithm doesn't update the paths, unless $d(v) + w\left((v,u)\right)$ is strictly less than the previous value $d(u)$, it will preserve the shortest (in length) paths and will thus not produce paths with zero-weighted cycles.


I'm not sure if I understand the second question. In some cases (when the zero cycle for example runs through the starting vertex), you can have a shortest path from the starting vertex to any other vertex that goes through this cycle arbitrary many times. Sometimes it is not possible, like here:

Not possible to have a shortest path with zero weighted cycle.