---
title: "Dijkstra shortest path (2074 Bhadra)"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:dijkstra-2074-bhadra"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/dijkstra-2074-bhadra
site: BCT Engineering
---

# Dijkstra shortest path (2074 Bhadra)

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2074 Bhadra, 8 marks
- Video: [Dijkstras Shortest Path Algorithm Explained | With Example | Graph Theory](https://www.youtube.com/watch?v=bZkzH5x0SKU) — FelixTechTips
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/dijkstra-2074-bhadra
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Use Dijkstra's algorithm to find the length of shortest path from vertex A to vertex Z in the following weighted graph. Also highlight the shortest path/paths in the graph. [Figure: weighted graph on vertices A, B, C, D, E, Z with edges A-B 6, A-C 8, B-C 6, B-D 7, B-E 5, C-D 10, C-E 9, D-E 5, D-Z 5, E-Z 8, an outer arc of weight 12 joining A to D and an outer arc of weight 11 joining C to Z [some edge placements unclear in scan]]

## Short answer

Dijkstra's algorithm yields a shortest path length of 17 from A to Z. The path is A–D–Z with weights 12 and 5.

## Answer

Dijkstra's algorithm (non-negative weights) labels every vertex with the best distance known so far and fixes one vertex at a time:
1. Give the source distance 0 and every other vertex ∞. All vertices are temporary.
2. Make the temporary vertex with the smallest label permanent.
3. For each temporary neighbour v of the new permanent vertex u: if d(u) + w(u,v) < d(v), set d(v) = d(u) + w(u,v) and record u as predecessor.
4. Repeat steps 2 and 3 until the target (or all vertices) is permanent.

#### Graph as read
Reading: the outer arc A–D has weight 12 and the outer arc C–Z has weight 11; the other eight edges are as listed.

Edges: A–B 6, A–C 8, B–C 6, B–D 7, B–E 5, C–D 10, C–E 9, D–E 5, D–Z 5, E–Z 8, A–D 12, C–Z 11.

#### Trace
Each cell shows label = distance(predecessor). **Bold** marks the vertex made permanent in that step; ✓ means already permanent.

| Step | Fixed | A | B | C | D | E | Z |
|---|---|---|---|---|---|---|---|
| 1 | A | **0** | 6(A) | 8(A) | 12(A) | ∞ | ∞ |
| 2 | B | ✓ | **6**(A) | 8(A) | 12(A) | 11(B) | ∞ |
| 3 | C | ✓ | ✓ | **8**(A) | 12(A) | 11(B) | 19(C) |
| 4 | E | ✓ | ✓ | ✓ | 12(A) | **11**(B) | 19(C) |
| 5 | D | ✓ | ✓ | ✓ | **12**(A) | ✓ | 17(D) |
| 6 | Z | ✓ | ✓ | ✓ | ✓ | ✓ | **17**(D) |

#### Result
Shortest distance from A to Z = **17**.

Shortest path (highlight these edges): **A → D → Z** with edge weights 12 + 5 = 17.

**Answer:** length of the shortest path A to Z = 17, along A–D–Z (the direct edge A–D = 12, then D–Z = 5). The route A–B–E–Z costs 19 and A–C–Z costs 19.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. At each step Dijkstra's algorithm makes permanent:
   A. The vertex with the most neighbours
   B. The vertex with fewest edges to the target
   C. The temporary vertex with the smallest label
   D. A vertex chosen at random
   Answer: C. The smallest temporary label is final when all weights are non-negative. (Key point: Dijkstra step)

2. A neighbour v of the newly fixed vertex u gets a new label when:
   A. w(u,v) < d(u)
   B. d(v) is already permanent
   C. d(u) > d(v)
   D. d(u) + w(u,v) < d(v)
   Answer: D. The label is replaced only if the route through u is shorter. (Key point: Relaxation)

3. The shortest distance from A to Z is:
   A. 19
   B. 18
   C. 11
   D. 17
   Answer: D. A-D is 12 and D-Z is 5, so 17. (Key point: Result)

4. Why is A-B-D-Z not chosen?
   A. It costs 6 + 7 + 5 = 18 > 17
   B. It costs 16
   C. D cannot be reached from B
   D. It uses a negative edge
   Answer: A. The direct A-D edge (12) beats going via B (13) to D. (Key point: Comparison)

5. The routes A-B-E-Z and A-C-Z both cost:
   A. 17
   B. 19
   C. 16
   D. 18
   Answer: B. 6 + 5 + 8 = 19 and 8 + 11 = 19. (Key point: Alternatives)

## Related in Discrete Structure

- [Dijkstra shortest path (2075 Bhadra)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2075-bhadra) — Discrete Structure, chapter 4
- [Dijkstra shortest path (2068 Bhadra)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2068-bhadra) — Discrete Structure, chapter 4, asked 4×
- [Dijkstra shortest path (2071 Bhadra)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2071-bhadra) — Discrete Structure, chapter 4, asked 4×
- [Dijkstra shortest path (2069 Bhadra)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2069-bhadra) — Discrete Structure, chapter 4, asked 4×
- [Dijkstra shortest path (2072 Asoj)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2072-asoj) — Discrete Structure, chapter 4
- [Dijkstra shortest path (2073 Magh)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2073-magh) — Discrete Structure, chapter 4

## Related in other subjects

- [Dijkstra's shortest paths from source F](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adijkstra-graph-source-f) — Data Structure and Algorithm, chapter 10
- [Dijkstra's shortest path algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adijkstra-algorithm-example) — Data Structure and Algorithm, chapter 10, asked 2×
- [Round Robin MST on 7-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Around-robin-mst-graph-l) — Data Structure and Algorithm, chapter 10
- [Kruskal's MST on 9-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-f) — Data Structure and Algorithm, chapter 10, asked 3×