# Negative edge weight in Dijkstra

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.

• 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. Commented Aug 1, 2021 at 12:36
• @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. Commented Aug 1, 2021 at 12:39
• 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.
– D.W.
Commented Aug 11, 2021 at 22:19