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?
Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph
algorithms;dynamic programming;shortest path
Hint: Try to modify the FloydWarshall 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$.