Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph

Question

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?

Answer 1

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$.

Answer 2

May be it helps you to see more easily the way to attack the problem. The first that you could try it's find or understand the recursive relation behind Floyd-Warshall Algorithm. As the next function $f$.

$$ f(u,v,k) = \begin{cases} w_{u,v} & k = 0\\ \min\, (\ f(u,v, k-1),\ f(u,k,k-1) + f(k,v,k-1)) & \text{otherwise} \end{cases} $$

• $w_{u,v}$ it's the weight of edge from $u$ to $v$ in the direct graph $G$. $\infty$ if that edge doesn't exist.
• $f(u,v,k)$ is the weight of a shortest path from $u$ to $v$ if you consider the first $k$ vertices as intermediates.

---

To adapt the above function form for your problem, I'd sketched the essence of the problem in the next graph:

• 
• $m_i\in E_0$
• $l_i\in E_1$
• The curly curve is the shortest path considering the first $k-1$ vertices.
• You have a alternate path that consider the $k$ node when you see the pattern (normal-$k$-dashed) lines in the path, or with convention above: (dashed-$k$-normal) line or $(m_i, l_j)^*$ , $(l_i, m_j)^*$ pattern in general.

So the next step it's construct the recursive relation looking the connection between subproblems, and for that you could think for a moment that your function solve the problem for a small size of problem, or instances pattern (follow principle of optimality).

$$ f(u,v,k,i) = \begin{cases} w_{u,v,i} & k = 0\\ \min\, (\ f(u,v, k-1,i),\ f(u,k,k-1,~i) + f(k,v,k-1,i)) & \text{otherwise} \end{cases} $$

• $w_{u,v,i}$ is the weight for the edge in $E_i$ (Note that I change enumeration of $E$ for convenience). $\infty$ if that edge doesn't exist.
• $f(u,v,k,i)$ is the weight of a shortest path that ended up with a edge in $E_i$ that consider the first $k$ vertices as intermediates like the graph above.
• $~i = 0$ if $i = 1$ or $1$ if $i = 0$.

So, the weight of the shortest alternate path from $u$ to $v$ is $$\min \,(\, f(u, v, |V|, 0),\ f(u, v, |V|, 1) )$$ where $|V|$ is the number of vertices.

Of course, after some work, you could notice that:

• It's possible delete parameter $k$
• you could implement iterative version or use a memorization technique.
• Other details, that I'm forgiving. It's late.

I'd wrote a python code/ and input test file if you can play with that. But, Here, it's not important.