Given two undirected graphs G1 = (V, E1) and G2 = (V, E2) over the same set of Vertices V and a weight function w : E1 ∪ E2 → R, let P = {e1, e2, . . . , en} be a path in (V, E1 ∪ E2)

P is an alternating path if for any 1 ≤ i < n at least one of the following two conditions hold:

ei ∈ E1, ei+1 ∈ E2

ei ∈ E2, ei+1 ∈ E1

Write a DP algorithm that given G1, G2, returns the weights of the shortest alternating paths between all pairs of vertices in V.