Q5(a) · Dijkstra algorithm

Answer

Definition. Dijkstra’s algorithm finds shortest paths from a source in a graph whose edge weights are nonnegative.

Simple meaning. Sabse chhota unfinished distance select karo, phir uske neighbours improve karo.

Understand it step by step

1. Initialize source distance 0, all others ∞, and no predecessors. No vertex is settled initially.
2. Select an unsettled vertex with minimum tentative distance. With nonnegative edges, its distance can now be finalized.
3. Relax each relevant outgoing edge: compare old distance with selected distance plus edge cost.
4. Repeat selection and relaxation. If all remaining distances are ∞, the remaining vertices are unreachable from the source.
5. Trace predecessors for the required destination. Always preserve arrow direction. Standard Dijkstra is not valid for graphs with negative edge costs.

Yaad rakho: Minimum tentative total choose; negative edges pe Dijkstra nahi.

Given

Edge	Cost
A→B	4
A→C	2
C→B	1
B→D	3
C→D	7

Source=A; target=D. Edges are directed; do not add reverse edges.

To find

The path A to D, its total cost and intermediate work.

Formula and why

LaTeX: d[v]\leftarrow\min(d[v],d[u]+w(u,v))

Use Dijkstra because all weights are nonnegative. Select the smallest unsettled total distance, not the cheapest isolated edge.

Swipe across the diagram to read its labels ↔

Diagram: Dijkstra · given directed graph. Labels: Dijkstra · given directed graph | Dijkstra · given directed graph | A | A | B | B | A->B | 4 | C | C | A->C | 2 | D | D | B->D | 3 | C->B | 1 | C->D | 7

Step-by-step solution

Step 1. Initialize

d[A]=0; every other distance=∞. No predecessors are known.

Vertex	Distance from A	Predecessor	State
A	0	—	Tentative
B	∞	—	Tentative
C	∞	—	Tentative
D	∞	—	Tentative

Step 2. Settle A at distance 0

Unsettled candidates before selection: A=0, B=∞, C=∞, D=∞. Select the minimum; ties use alphabetical order.

Edge	Old distance	Candidate	Decision
A→B	∞	0+(4)=4	Improve to 4; predecessor=A
A→C	∞	0+(2)=2	Improve to 2; predecessor=A

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	4	A	Tentative
C	2	A	Tentative
D	∞	—	Tentative

Step 3. Settle C at distance 2

Unsettled candidates before selection: B=4, C=2, D=∞. Select the minimum; ties use alphabetical order.

Edge	Old distance	Candidate	Decision
C→B	4	2+(1)=3	Improve to 3; predecessor=C
C→D	∞	2+(7)=9	Improve to 9; predecessor=C

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	3	C	Tentative
C	2	A	Settled
D	9	C	Tentative

Step 4. Settle B at distance 3

Unsettled candidates before selection: B=3, D=9. Select the minimum; ties use alphabetical order.

Edge	Old distance	Candidate	Decision
B→D	9	3+(3)=6	Improve to 6; predecessor=B

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	3	C	Settled
C	2	A	Settled
D	6	B	Tentative

Step 5. Settle D at distance 6

Unsettled candidates before selection: D=6. Select the minimum; ties use alphabetical order.

No outgoing edges to relax.

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	3	C	Settled
C	2	A	Settled
D	6	B	Settled

Step 6. Recover the path

Trace backwards: D ← B ← C ← A. Reverse it: A → C → B → D.

Edge sum: 2 + 1 + 3 = 6.

Final answer: A → C → B → D; cost=6.