Question

For the network below, the objective is to find the length of the shortest path from node P to node G. Let $d_{ij}$ be the length of directed arc from node i to node j.


Let $s_j$ be the length of the shortest path from P to node j. Which of the following equations can be used to find $S_G?$

• A. $S_G=Min\{S_Q,S_R\}$
• B. $S_G=Min\{S_Q+d_{QG},S_R+d_{RG}\}$
• C. $S_G=Min\{S_Q-d_{QG},S_R+d_{RG}\}$
• D. $S_G=Min\{d_{QG},d_{RG}\}$

Answer 1

The correct option is B $S_G=Min\{S_Q+d_{QG},S_R+d_{RG}\}$



$d_{ij}=\text{length of direction from node i to node j.}$

$S_j=\text{length of shortest path from P to node j.}$

$\text{There will be two possible paths to reach from P to G.}$

$\text{1. By reaching (P to Q) then (Q to G)}$

$\text{2. By reaching (P to R) then (R to G)}$

then,

$S_G=\{S_Q+d_{OG},S_R+d_{RG}\}$