Discussion
V = {A, B, C, D, E, F, G, H, I}
E = {e1 = (A, B), e2 = (A, C), e3 = (A, D), e4 = (B, C), e5 = (B, F), e6 = (B, H), e7 = (C, D), e8 = (C, E), e9 = (C, F), e10 = (D, E), e11 = (D, I), e12 = (E, F), e13 = (E, G), e14 = (F, G), e15 = (F, H), e16 = (G, H), e17 = (G, I), e18 = (H, I)}
W = {22, 9, 12, 35, 36, 34, 4, 33, 30, 18, 23, 24, 39, 25, 21, 19}
The weight of the shortest path from node A to I in the undirected graph is........... .
Answer: C
The shortest path from A to I has weight 42.
Reading the weights from the figure, the cheap edges near A are A-C (9), A-D (12) and C-D (4), and D connects straight to I with weight 30. Running Dijkstra's algorithm from A:
- A = 0; then C = 9, D = 12 (A-C-D would be 13), B = 22.
- From D: I = 12 + 30 = 42 and E = 12 + 33 = 45.
- Every other route to I is longer: through H it is at least 22 + 34 + 19 = 75, and through G at least 45 + 23 + 21 = 89.
\[ \begin{aligned} d(A,I) &= w(A,D) + w(D,I) \\ &= 12 + 30 = 42 \end{aligned} \]
43 is the path A-C-D-I, \(9 + 4 + 30\), which looks attractive because it starts with the cheapest edge but ends one unit heavier. 2 and 3 count edges rather than adding weights: A-D-I has two edges.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development