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

ignougroup
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

Leave a Reply