--- title: "Dijkstra's shortest paths from source F" subject: "Data Structure and Algorithm" chapter: 10 key: "semester_4/data_structure_and_algorithm:dijkstra-graph-source-f" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/dijkstra-graph-source-f site: BCT Engineering --- # Dijkstra's shortest paths from source F Data Structure and Algorithm · Chapter 10: Graphs - Asked in: 2071 Bhadra, 2+4 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/data_structure_and_algorithm/dijkstra-graph-source-f - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10 ## Question Discuss Dijkstra's shortest path algorithm. Find the shortest paths for given graph with source node 'F' using Dijkstra's algorithm. [Figure: directed weighted graph with edges A→B 2, C→A 6, D→B 11, F→A 7, F→C 3, E→C 5, D→F 9, F→E 1] ## Short answer Dijkstra's algorithm repeatedly selects the vertex with smallest tentative distance, finalizes it, and relaxes outgoing edges. From F, shortest distances: E=1 (F-E), C=3 (F-C), A=7 (F-A), B=9 (F-A-B), D=∞ (unreachable). ## Answer **Dijkstra's algorithm** finds the shortest path from a source vertex to all other vertices in a graph with non-negative weights. Keep dist[v] = ∞ for all except the source (0). Repeatedly select the unfinalised vertex u with the smallest dist, finalise it, and relax each outgoing edge (u, v, w): if dist[u] + w < dist[v], set dist[v] = dist[u] + w. Time O(V²) with an array. #### Given directed graph Edges: A→B 2, C→A 6, D→B 11, F→A 7, F→C 3, E→C 5, D→F 9, F→E 1. Source = F. | Step | Selected | A | B | C | D | E | F | |---|---|---|---|---|---|---|---| | Init | - | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | | 1 | F (0) | 7 | ∞ | 3 | ∞ | 1 | 0 | | 2 | E (1) | 7 | ∞ | 3 | ∞ | 1 | 0 | | 3 | C (3) | 7 (3+6 = 9 is worse) | ∞ | 3 | ∞ | 1 | 0 | | 4 | A (7) | 7 | 9 | 3 | ∞ | 1 | 0 | | 5 | B (9) | 7 | 9 | 3 | ∞ | 1 | 0 | | 6 | D (∞) | 7 | 9 | 3 | ∞ | 1 | 0 | In step 2, E→C gives 1 + 5 = 6, which is not better than 3. **Shortest distances from F:** | Destination | Distance | Path | |---|---|---| | E | 1 | F-E | | C | 3 | F-C | | A | 7 | F-A | | B | 9 | F-A-B | | D | ∞ | no path (D has no incoming edge) | ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does Dijkstra's algorithm require and compute? A. Shortest path to one vertex only, with unweighted edges B. Minimum spanning tree, with any weights C. Shortest paths from a source to all vertices, with non-negative weights D. All-pairs shortest paths, with negative weights allowed Answer: C. It finds single-source shortest paths and needs non-negative edge weights. (Key point: Dijkstra purpose and condition) 2. What does the algorithm do repeatedly? A. Pick the unfinalised vertex with smallest dist, finalise it, relax its outgoing edges B. Pick vertices in alphabetical order C. Pick the vertex with largest dist and relax all edges into it D. Sort all edges and add those without cycles Answer: A. It selects the minimum-dist vertex and relaxes each outgoing edge if dist[u]+w < dist[v]. (Key point: Algorithm step) 3. Why is dist[C] kept at 3 and not updated through E? A. E is not finalised B. E has no edge to C C. E->C gives 1+5 = 6, which is not better than 3 D. C is the source Answer: C. Relaxation only updates when the new sum is smaller; 6 is larger than 3. (Key point: Distance to C) 4. What is the shortest distance and path from F to B? A. 11 via F-C-D-B B. 9 via F-A-B C. 13 via F-C-A-B D. 7 via F-A Answer: B. F-A is 7 and A-B is 2, giving 9; the route via C gives 3+6+2 = 11. (Key point: Distance to B) 5. Why is D at infinity from source F? A. D was finalised first B. D equals the source C. Edge weights to D are negative D. D has no incoming edge, so no path reaches it Answer: D. D only has outgoing edges (D->B, D->F), so F cannot reach it. (Key point: Unreachable vertex) ## Related in Data Structure and Algorithm - [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× - [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 - [Kruskal's MST on 7-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-74) — Data Structure and Algorithm, chapter 10, asked 3× - [Kruskal's MST on graph A to G](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Akruskal-mst-graph-d) — Data Structure and Algorithm, chapter 10, asked 3× - [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 ## Related in other subjects - [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 (2072 Asoj)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2072-asoj) — Discrete Structure, chapter 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 (2071 Bhadra)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adijkstra-2071-bhadra) — Discrete Structure, chapter 4, asked 4×