Good day,
I am currently going over some problems from my optimisation class and I can not seem to figure this one out.
Assume that in the Shortest Path Problem, Bellman-Ford terminates but some vertices still remain unchanged i.e. $y_v=\infty$ for some $v\in V$
Show that $\exists \ X\subset V $ such that $c(uv)=\infty \ \forall \ uv \in A, \ u \in X, \ v\in V\setminus X $ (there is a subset $X$ such that the cost of each edge with one vertex in $X$ and one outside of it is $\infty$).
I am not really sure how to get started on this one.
Best Answer
I think what might help you is the following:
The Bellman-Ford algorithm computes one-to-all shortest paths by repeated relaxation. If at the end of the algorithm some vertices still have value $\infty$, then those vertices must be in a different connected component than the starting vertex $a$. Otherwise they would have been reached over some path starting from $a$ and then they wouldn't have value $\infty$ anymore.
Now to solve this you have to somehow define your set $X$. I suggest you try with $X = \{ v \in V \text{ such that v has value } \infty \text{ when Bellman-Ford has terminated} \}$.
(The cost of an edge between to vertices $u, v$ is considered $\infty$ if in the original graph there is no such edge. At least that's what I assume. The transformation from no edge to an edge with value $\infty$ is made for Bellman-Ford to operate on the graph.)