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

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?

• Do you know a DP algorithm for the regular APSP problem? – Raphael Dec 3 '14 at 11:32
• Which textbook did you read the exercise? : – jonaprieto Dec 4 '14 at 3:25

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

• Where did you find this? You don't need the $k$. It will do to use an array $A[i,j,s,e]$ with $s$ and $e$ booleans. – reinierpost Nov 24 '14 at 16:55
• It's true that you can implement the algorithm without keeping the entire matrix, so in terms of memory it's $n^2$ rather than $n^3$. But if you wanted to keep the shortest paths themselves, it's easier with the larger matrix. – Yuval Filmus Nov 24 '14 at 18:40
• I don't understand - you'll be keeping one point on the path, not full paths. The number of paths is exponential in general. – reinierpost Nov 25 '14 at 7:26
• Yes, but you could use the big table to either store all paths succinctly, or store one shortest path between any two vertices succinctly. – Yuval Filmus Nov 25 '14 at 14:32

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.