Answer to Question #100454 in Java | JSP | JSF for Kyrelle T

Question

Give an example graph in which Dijkstra’s algorithm gives the wrong answer in the presence of a negative cost edge but no negative-cost cycle

Answer 1

The easiest graph I can imagine is this:

The adjacency matrix:

	A	B	C
A	0	10	15
B	∞	0	∞
C	∞	-7	0

If you want to go from vertex A to vertex B, Dijkstra algoritm will choose path A->B with weight 10. Edge (A,C) has bigger weight (15), so it will be marked as not the shortest and algorithm will not go to vertex C and will not find out that edge (C,B) has weight -7. So it will not find the shortest path A->C->B (total weight 8).

If you want graph that looks more complicated:

The adjacency matrix:

	A	B	C	D	E	F
A	0	25	∞	∞	∞	15
B	25	0	-10	∞	∞	∞
C	∞	-10	0	10	5	5
D	∞	∞	10	0	-10	∞
E	∞	∞	5	-10	0	30
F	15	∞	5	∞	30	0

Algorithm will not find the shortest path from vertex A vertex to vertex E. The correct answer is A->B->C->D->E (total weight 15), instead of this algorithm will find A->F->C->E (total weight 25).