[Solved]: Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph

Problem Detail: 

I'm learning Dynamic Programming (By myself) and in the textbook there is this question:

Given two undirected graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ over the same set of Vertices $V$ and a weight function $w: E_1 \cup E_2 \rightarrow \mathbb{R}$, let $P = \left\{e_1, e_2, ..., e_n \right\}$ be a path in $(V, E_1 \cup E_2)$.

We sat that P is alternating if for any $1 \leq i < n$ at least one of the following two conditions hold:

• $e_i \in E_1, e_{i+1} \in E_2$
• $e_i \in E_2, e_{i+1} \in E_1$

Write a DP algorithm that given $G_1, G_2$, returns the weights of the shortest alternating paths between all pairs of vertices in $V$

OK so I sat on this question for a long time but I can't seem to figure out how to do solve it. Since this is a shortest path between all pairs I tried to think of a solution which uses Floyd-Warshall algorithm, but I can't figure out how to factor in the addition of the alternating path.

Every solution I think of fails when inserting special Edge Cases.

Can anyone give a hint as to how to proceed?

Asked By : user475680

Answered By : Yuval Filmus

Hint: Try to modify the Floyd–Warshall algorithm to account for edge types. As described in Wikipedia, we construct an array $A[i,j,k]$ which keeps the weight of the shortest path from $i$ to $j$ via the vertices $1,\ldots,k$. Instead, construct an array $A[i,j,k,x,y]$ which keeps the weight of the shortest path from $i$ to $j$ via the vertices $1,\ldots,k$ whose first edge belongs to $G_x$, and whose last edge belongs to $G_y$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33476