Let $G=(V,E)$ a directed graph with weight function $w:E \to R$. let $s \in V$ a vertex s.t it has path to any other vertex in $G$. Suppose that every negative vertex in this graph is bridge edge, means $(u,v)$ is bridge if there exists cut (S,T) s.t $S \subseteq V, T \subseteq V$ and $S \cap T = \emptyset, S \cup T = V$. How can i show that dijkstra's algorithm is correct in that case? I tried to rely on the proof given in CLRS book and to modify it, but got stuck in proving it.
$\begingroup$
$\endgroup$
1
New contributor
csmathstudent8 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
-
$\begingroup$ (I'd much prefer "s.t." for such that.) $\endgroup$– greybeardCommented Dec 7 at 7:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The standard proof should work.
By induction on the size of $S$, the vertices that have been popped from the priority queue. Base case is the same, induction hypothesis is the same. Induction step is the same, with one minor modification.
Suppose you pop vertex $v$ and its distance was set by a predecessor $u$. By IH the distance $d(s, u)$ is correct, and suppose that $d(s,v)=d(s,u)+w(uv)$ is not correct, ie that there is a path from $s$ to $v$ using less than the current cost.
Here you use the fact that any other path from $s$ to $v$, if it leaves $S$ cannot have a negative edge since it wouldn't be a bridge.
-
$\begingroup$ Well the proof i know differs from yours, let P be the lightest path from s to u, and mark y as the first vertex that's not in S, and then showing that $\delta(s,y) = dist(y)$, now i want to show that it's not possible that we have a negative path from y to u. $\endgroup$ Commented Dec 7 at 11:51
-
$\begingroup$ But it is possible to have a negative path, and that's not a problem. What you have to show is that it there are two paths from $S$ to $y$, then there are no negative edges. $\endgroup$ Commented Dec 7 at 15:18
-
$\begingroup$ What i wanted to show in my proof, logically, that it's impossibe to have a negative vertex between y and u, because if there was it would violate the bridge property. $\endgroup$ Commented Dec 7 at 15:27
-
$\begingroup$ But that's neither what you want to prove nor true. You want to show that any alternative path from $S$ to $y$ cannot have a negative edge. $\endgroup$ Commented Dec 7 at 18:38