Dijkstra’s algorithm on directed graph with negative edges – expected output?

Question

Comments

1+2+8-4 = 7

---

1+2+8-4 = 7

---

After solving, I saw that dijkstra's algorithm gives the path including -4 as the answer. The path being:
a → d → e → g → h

Path cost = 7

Answer 1

✅ Dijkstra’s Algorithm Execution Table (Source = a)

Step	Selected Node	a	b	c	d	e	f	g	h
Init	—	0	∞	∞	∞	∞	∞	∞	∞
1	a	0	∞	∞	1	∞	∞	∞	∞
2	d	0	∞	3	1	3	11	∞	∞
3	c	0	∞	3	1	3	11	∞	∞
4	e	0	∞	3	1	3	6	∞	∞
5	f	0	∞	3	1	3	6	11	8
6	i	0	∞	3	1	3	6	11	9
7	g	0	∞	3	1	3	6	11	9

---

✅ Final Output (as per Dijkstra)

Vertex	Shortest Distance
a	0
b	∞
c	3
d	1
e	3
f	6
g	11
h	9

---

⚠️ Important Note

• The real shortest path to h is 7,

• But Dijkstra gives 9 because it fails in presence of negative edge (g → h = –4).

---

FINAL ANSWER IS 9

Answer 2

Here is a to h minimum distance is 9 , because we have to find the minimum path that traverse to minimum edge of every node ..