GATE 2018 ME (ME2) – Question 61
Arc labels give lengths in the shown directed project graph. Find the shortest path length from node 1 to node 6.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 7 to 7 OR 11 to 11
Explanation
Start with distance zero at node 1. Then $d_2=2$, $d_3=\min(4,2+1)=3$, $d_5=\min(2+2,3+3)=4$ and $d_4=\min(2+4,4+1)=5$. Finally $d_6=\min(5+2,4+4)=7$. Shortest path is **1 → 2 → 5 → 4 → 6, length 7**. The official key also accepts 11, which is the longest path 1 → 3 → 5 → 4 → 6; both grading alternatives are preserved.