ezzr's blog

By ezzr, history, 6 weeks ago, In English

Recently faced with the following problem: given a directed weighted graph (all weights are positive and less than 100), you need to find the shortest path between vertices 1 and n such that the length of the path between any two vertices on this path is not divisible by 13. The number of vertices in the graph is not more than 50.

How can I do that?

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem Source

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Denote $$$p = 13$$$, $$$n$$$ -- number of vertices, $$$m$$$ -- number of edges.

First of all, note that sum of weights on some subpath is divisible by $$$p$$$ if and only if there are two prefixes of path with same remainder modulo $$$p$$$.

Let $$$f(i, S, d)$$$ be the shortest path $$$1 \leadsto i$$$, such that $$$S$$$ is set of remainders of its prefixes, $$$d$$$ is remainder of its length. So answer is minimum of values of $$$f$$$ for vertex $$$n$$$.

Like in Ford-Bellman Algorithm on $$$k$$$-th step we want count values of $$$f$$$ for $$$|S| \leqslant k$$$,

So we initialize $$$f(1, \varnothing, 0) = 0$$$ and all others with infinity.

On $$$k$$$-th step we will iterate through all edges. Consider edge $$$v \to u$$$ with weight $$$w$$$. So we should relax $$$f(u, S \cup { ((d + w) \mod p) }, ((d + w) \mod p))$$$ with $$$f(v, S, d) + w$$$ for all $$$d, S$$$ such that $$$d + w \not\equiv 0 \pmod{p}$$$ and $$$(d + w) \mod p$$$ is not in $$$S$$$.

Relaxing values for one edge will take at most $$$O(p 2^p)$$$ time, and we have $$$n - 1$$$ iterations, so it is $$$O(nmp2^p)$$$. But we can notice, that $$$p$$$ iterations will be sufficient, so it is $$$O(mp^2 2^p)$$$.

But on $$$k$$$-th iteration we can look only at such $$$S$$$ that $$$|S| = k - 1$$$, so with accurate implementation it will be $$$O(mp2^p)$$$, which should be sufficient for your constraints. Also it is not hard to recover answer from this "dp".

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think teachers will explain how to solve this on next sunday