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

# Dijkstra shortest path (2075 Bhadra)

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2075 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-2075-bhadra
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Use Dijkstra's algorithm to find the length of a shortest path from the vertices A to other in the graph below. [Figure: weighted undirected graph on vertices A, B, C, D, E, F, G, H with edges A-B 10, A-G 5, A-H 8, B-C 3, B-H 4, B-D 6, C-H 4, C-D 3, G-H 4, G-F 3, H-F 10, H-E 4, H-D 9, F-D 2, F-E 3, E-D 1; edge readings approximate from scan]

## Short answer

Using Dijkstra's algorithm, the shortest distances from A are: B=10, C=12, D=10, E=11, F=8, G=5, H=8. The paths are A–B, A–H–C, A–G–F–D, A–G–F–E or A–G–F–D–E, A–G–F, A–G, and A–H respectively.

## 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
The figure is read with the edge weights listed below (the scan is approximate). Source is A; distances to all other vertices are required.

Edges: A–B 10, A–G 5, A–H 8, B–C 3, B–H 4, B–D 6, C–H 4, C–D 3, G–H 4, G–F 3, H–F 10, H–E 4, H–D 9, F–D 2, F–E 3, E–D 1.

#### 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 | F | G | H |
|---|---|---|---|---|---|---|---|---|---|
| 1 | A | **0** | 10(A) | ∞ | ∞ | ∞ | ∞ | 5(A) | 8(A) |
| 2 | G | ✓ | 10(A) | ∞ | ∞ | ∞ | 8(G) | **5**(A) | 8(A) |
| 3 | F | ✓ | 10(A) | ∞ | 10(F) | 11(F) | **8**(G) | ✓ | 8(A) |
| 4 | H | ✓ | 10(A) | 12(H) | 10(F) | 11(F) | ✓ | ✓ | **8**(A) |
| 5 | B | ✓ | **10**(A) | 12(H) | 10(F) | 11(F) | ✓ | ✓ | ✓ |
| 6 | D | ✓ | ✓ | 12(H) | **10**(F) | 11(F) | ✓ | ✓ | ✓ |
| 7 | E | ✓ | ✓ | 12(H) | ✓ | **11**(F) | ✓ | ✓ | ✓ |
| 8 | C | ✓ | ✓ | **12**(H) | ✓ | ✓ | ✓ | ✓ | ✓ |

#### Result

| Vertex | Shortest distance from A | Shortest path |
|---|---|---|
| B | 10 | A–B |
| C | 12 | A–H–C |
| D | 10 | A–G–F–D |
| E | 11 | A–G–F–D–E or A–G–F–E |
| F | 8 | A–G–F |
| G | 5 | A–G |
| H | 8 | A–H |

**Answer:** shortest distances from A: B = 10, C = 12, D = 10, E = 11, F = 8, G = 5, H = 8. (E has two shortest paths of length 11: A–G–F–E and A–G–F–D–E.)

## 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 temporary vertex with the smallest label
   C. The vertex with fewest edges to the target
   D. A vertex chosen at random
   Answer: B. 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) + w(u,v) < d(v)
   D. d(u) > d(v)
   Answer: C. The label is replaced only if the route through u is shorter. (Key point: Relaxation)

3. From A, the shortest distance to F is:
   A. 13
   B. 10, via A-H-F
   C. 8, via A-G-F
   D. 18
   Answer: C. A-G is 5 and G-F is 3 giving 8; A-H-F costs 18. (Key point: Result)

4. Shortest distance from A to C and its route:
   A. 13 via A-B-C
   B. 13 via A-G-F-D-C
   C. 10 via A-B
   D. 12 via A-H-C
   Answer: D. A-H is 8 and H-C is 4 giving 12; the other routes cost 13. (Key point: Result)

5. Vertex E has distance 11 because:
   A. F is at 8 and F-E is 3, with D (10) + 1 also giving 11
   B. H is at 8 and H-E is 4 giving 12 is shortest
   C. A-E is a direct edge of 11
   D. Only one path exists
   Answer: A. Both A-G-F-E and A-G-F-D-E have length 11. (Key point: Multiple paths)

## Related in Discrete Structure

- [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 (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 (2070 Magh)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2070-magh) — 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

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