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

# Dijkstra shortest path (2070 Magh)

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2070 Magh, 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-2070-magh
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Use Dijkstra's algorithm to find the length of the shortest path between the vertices a and z in the weighted graph displayed below. [Figure: weighted graph on vertices a, b, c, d, e, z with edges a-c 3, a-b 6, c-b 4, c-e 11, b-e 8, b-d 7, e-d 5, e-z 10, d-z 4]

## Short answer

The shortest path length from a to z is 17, via a–b–d–z.

## 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
Source a, target z.

Edges: a–c 3, a–b 6, c–b 4, c–e 11, b–e 8, b–d 7, e–d 5, e–z 10, d–z 4.

#### 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) | 3(a) | ∞ | ∞ | ∞ |
| 2 | c | ✓ | 6(a) | **3**(a) | ∞ | 14(c) | ∞ |
| 3 | b | ✓ | **6**(a) | ✓ | 13(b) | 14(c) | ∞ |
| 4 | d | ✓ | ✓ | ✓ | **13**(b) | 14(c) | 17(d) |
| 5 | e | ✓ | ✓ | ✓ | ✓ | **14**(c) | 17(d) |
| 6 | z | ✓ | ✓ | ✓ | ✓ | ✓ | **17**(d) |

#### Result
Shortest distance from a to z = **17**.

Shortest path (highlight these edges): **a → b → d → z** with edge weights 6 + 7 + 4 = 17.

**Answer:** shortest path length = 17 along a → b → d → z (6 + 7 + 4). By comparison, the route a–c–e–z costs 3 + 11 + 10 = 24.

## 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. Shortest distance from a to z:
   A. 17, along a-b-d-z
   B. 24 along a-c-e-z
   C. 14
   D. 18
   Answer: A. 6 + 7 + 4 = 17; a-c-e-z costs 3 + 11 + 10 = 24. (Key point: Result)

4. What is the final label of b, and why?
   A. 7 via c
   B. 6, direct from a (a-c-b gives 7)
   C. 3
   D. 4
   Answer: B. The direct edge a-b = 6 beats 3 + 4 = 7. (Key point: Labels)

## Close variants set in other exams

- [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 (2068 Bhadra)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2068-bhadra) — Discrete Structure, chapter 4, asked 4×

## Related in Discrete Structure

- [Dijkstra shortest path (2073 Magh)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2073-magh) — Discrete Structure, chapter 4
- [Dijkstra shortest path (2074 Bhadra)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2074-bhadra) — Discrete Structure, chapter 4
- [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 (2072 Asoj)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2072-asoj) — Discrete Structure, chapter 4

## Related in other subjects

- [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×
- [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
- [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×
- [MST definition; Kruskal's MST on 6-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amst-definition-kruskal-graph-i) — Data Structure and Algorithm, chapter 10