# Shortest path with multiple source and multiple sink

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?

• seems fine for me – Thomas Lesgourgues Oct 29 '19 at 13:29