3
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – reinierpost Nov 24 '14 at 16:55
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 24 '14 at 18:40
  • $\begingroup$ I don't understand - you'll be keeping one point on the path, not full paths. The number of paths is exponential in general. $\endgroup$ – reinierpost Nov 25 '14 at 7:26
  • $\begingroup$ Yes, but you could use the big table to either store all paths succinctly, or store one shortest path between any two vertices succinctly. $\endgroup$ – Yuval Filmus Nov 25 '14 at 14:32
2
$\begingroup$

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:

  • enter image description here
  • $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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.