snippetMajor
Example of a graph with negative weighed edges in which Dijkstra's algorithm does work
Viewed 0 times
edgesgraphdijkstraweighedwithexamplealgorithmworkdoeswhich
Problem
I was asked to give an example of a graph that has edges with negative weight, but Dijkstra's algorithm will still give us the correct output. It was part of a prove/disprove question. The claim was.. "If a graph has negative edges, Dijkstra's algorithm will return the wrong output".
Solution
Take a look at the simplest possible example: Our graph has only two nodes: $s,t$, and a single edge between them.
In this example, it won't matter what is the cost of this single edge (it can be negative), and Djikstra will always return the only single path between $s$ and $t$: which is directly $s\rightarrow t$.
In this example, it won't matter what is the cost of this single edge (it can be negative), and Djikstra will always return the only single path between $s$ and $t$: which is directly $s\rightarrow t$.
Context
StackExchange Computer Science Q#143297, answer score: 39
Revisions (0)
No revisions yet.