Suppose given an un-directed graph $G$, such that bridge edge of $G$ has negative weight.

From Wikipedia:

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components.

Now there is a claim:

The Dijkstra find correct shortest simple-path if the bridge edge has negative weight.

I think this claim is correct, but i can't show it. Already i know that, if edges of source $s$ have negative weight, then Dijkstra can find correct shortest path.

  • 1
    $\begingroup$ However you can walk from "side-to-side" on the edge, decreasing the total cost with each time. If the edge was directed, then its a different problem. $\endgroup$
    – nir shahar
    Commented Aug 1, 2021 at 12:36
  • $\begingroup$ @Rostami.M The claim is false, as nir shahar pointed out. Also, it's a bit pedantic but notice that, in the claim, we are not promised anything about the weights of the other (non-bridge) edges so, for example, it is conceivable that all edge weights of $G$ are negative. $\endgroup$
    – Steven
    Commented Aug 1, 2021 at 12:39
  • $\begingroup$ Please don't use the comments for extended discussion or back-and-forth conversations. Instead, we want you to revise the question to address the feedback, then flag comments as 'no longer needed'. Comments exist to help you improve your question, not as a means for interactive help or additional questions. $\endgroup$
    – D.W.
    Commented Aug 11, 2021 at 22:19
  • $\begingroup$ Please write your answer in the 'answer box'; don't answer in the comments. Thank you. $\endgroup$
    – D.W.
    Commented Aug 13, 2021 at 17:08
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – D.W.
    Commented Aug 13, 2021 at 17:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.