---
title: "Dijkstra's shortest path algorithm"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:dijkstra-algorithm-example"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/dijkstra-algorithm-example
site: BCT Engineering
---

# Dijkstra's shortest path algorithm

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2069 Bhadra, 5 marks; 2069 Poush, 6 marks (asked 2 times)
- 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/data_structure_and_algorithm/dijkstra-algorithm-example
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Discuss Dijkstra's shortest path algorithm with suitable example.

## Short answer

Dijkstra repeatedly selects the unvisited vertex with smallest tentative distance, finalizes it, and relaxes neighbors. From source A, distances are A=0, C=2, B=3 via C, D=8 via B, E=10 via D. Works only on non-negative weights.

## Answer

**Dijkstra's algorithm** finds the shortest paths from one source vertex to all other vertices in a weighted graph with non-negative edge weights. It is greedy: it repeatedly selects the unvisited vertex with the smallest known distance, finalises it, and **relaxes** (updates) the distances of its neighbours.

#### Algorithm
```text
DIJKSTRA(G, s)
1. for each vertex v: dist[v] = infinity, prev[v] = none
2. dist[s] = 0;  S = empty set
3. while S does not contain all vertices
4.     u = vertex not in S with minimum dist[u];  add u to S
5.     for each neighbour v of u not in S
6.         if dist[u] + w(u,v) < dist[v]
7.             dist[v] = dist[u] + w(u,v);  prev[v] = u
```
Time: O(V²) with an array, O(E log V) with a binary heap.

#### Example
Undirected graph with edges A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2. Source = A.

| Step | Vertex selected | dist A | dist B | dist C | dist D | dist E |
|---|---|---|---|---|---|---|
| Init | - | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | A (0) | 0 | 4 | 2 | ∞ | ∞ |
| 2 | C (2) | 0 | 3 (via C) | 2 | 10 | 12 |
| 3 | B (3) | 0 | 3 | 2 | 8 (via B) | 12 |
| 4 | D (8) | 0 | 3 | 2 | 8 | 10 (via D) |
| 5 | E (10) | 0 | 3 | 2 | 8 | 10 |

**Shortest paths from A:**
- A to C: 2 (A-C)
- A to B: 3 (A-C-B)
- A to D: 8 (A-C-B-D)
- A to E: 10 (A-C-B-D-E)

Dijkstra fails with negative edge weights (Bellman-Ford is used instead).

## Check yourself

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

1. What does Dijkstra do each step?
   A. Select the largest
   B. Select the unvisited vertex with smallest distance and relax its neighbours
   C. Select randomly
   D. Sort edges
   Answer: B. Greedy selection. (Key point: Dijkstra step)

2. What is a limitation?
   A. Fails on undirected graphs
   B. Fails on cycles
   C. Fails with negative edge weights
   D. Requires a tree
   Answer: C. Use Bellman-Ford. (Key point: Negative weights)

3. Shortest distance A to B in the example?
   A. 4
   B. 5
   C. 2
   D. 3 via A-C-B
   Answer: D. 2+1 = 3 beats direct 4. (Key point: Distance to B)

4. Shortest distance A to E?
   A. 10
   B. 12
   C. 8
   D. 9
   Answer: A. A-C-B-D-E = 2+1+5+2 = 10. (Key point: Distance to E)

## Related in Data Structure and Algorithm

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

## Related in other subjects

- [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 (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 (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×