Given two undirected graphs G1 = (V, E1) and G2 = (V, E2) over the same set
Fantastic news! We've Found the answer you've been seeking!
Question:
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.
Related Book For
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi
Posted Date: