(15 points) 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 .