# Q5(a) · Dijkstra algorithm

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2025-legacy-reexam/q5a

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2025-legacy-reexam--q5a/

Actual paper; 100 marks attempted. Current-syllabus alignment is stated per question.

### Q5(a). Explain the Dijkstra’s algorithm with an example. [10 marks]

### 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.

#### Practical example

If tentative distances are B=4, C=2 and D=∞, settle C next. You choose using total source-to-vertex cost 2, not the smallest individual edge anywhere in the graph.

1. Set source to 0 and other distances to infinity.
2. Repeatedly choose the unsettled vertex with minimum tentative distance.
3. Settle it and relax its outgoing edges.
4. Recover paths using predecessors.

The standard algorithm requires nonnegative edge weights.

**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



$$
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 ↔

![Dijkstra · given directed graph](https://deep-learning-study-room.vercel.app/cn/fig/dijkstra-1.973d01595e.svg)

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

Read the labels and direction before substituting numbers.

## 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.

#### What this result means

The predecessor table proves which edges make the route. A table containing only the final cost is not the complete working requested.