Let $G = (V,A)$ be a directed graph with arc costs $c_{ij}$, for $(i,j) \in A$. Suppose that you want to find a shortest path in $G$ that can start at either of the nodes $s_1$ or $s_2$ and can terminate at either of the nodes $t_1$ or $t_2$. How would you solve this problem?

My thoughts: Assign a dummy source $s_0$ and dummy end $t_0$ and link $s_0$ with $s_1$ or $s_2$ with 0 wieght links and similarly connect $t_0$ with $t_1$ and $t_2$ with 0 cost links and solve a shortest path linear program taking $s_0$ as my start and $t_0$ as my end. Am I missing anything?

  • 2
    $\begingroup$ seems fine for me $\endgroup$ – Thomas Lesgourgues Oct 29 '19 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.