Let $G$ be a graph whose edges have integer weights between 1 and 255.

What is an efficient algorithm for finding a path between two vertices $s,t$, such that the product of weights on the path is minimized?

The first approach that comes to mind is to replace each weight with its logarithm, and use e.g. Dijkstra's algorithm for finding a path that minimizes the sum of weights. The run-time complexity is $O(|E|+|V|\log|V|)$. For practical purposes this is a good solution, but theoretically it does not solve the problem, since the logarithm (when represented as a floating-point number) is not accurate.

A second approach is to use Dijkstra's algorithm directly, replacing each "+" operation with "*" and each "0" with "1" (equivalently, replace each weight with its logarithm but represent the logarithm of $x$ as "$\log{x}$" and sum the weights using the rule $\log{x}+\log{y}=\log{xy}$). The problem is that, with integer multiplication, the weights might grow very fast: even though each weight is represented by $O(1)$ bits, the product of a path might require $O(n)$ bits to represent, and this affects the runtime complexity of multiplication.

Is there a more efficient algorithm?

  • $\begingroup$ This seems like a practical question. In theory, log doesn't lose anything. You store everything in the form "$\log x$", and use the addition rule $\log x + \log y = \log xy$. $\endgroup$ – Yuval Filmus Apr 10 '19 at 13:33
  • $\begingroup$ From a practical point of view, I'm not so sure that you lose accuracy. Floating point numbers have a very reasonable amount of precision. $\endgroup$ – Yuval Filmus Apr 10 '19 at 13:34
  • $\begingroup$ @YuvalFilmus the point of taking the logarithm is to do the algorithm with additions, which are faster than multiplications. If you present the log as $\log x$, you still need to do multiplications.. $\endgroup$ – Erel Segal-Halevi Apr 10 '19 at 14:40
  • $\begingroup$ Instead of performing a multiplication "all at once", it might be possible to calculate it incrementally, so that at any given time, you have an interval which is certain to contain the true answer, and as you perform more work the interval narrows. Initially the interval is wide and requires few bits to represent approximately. To choose the edge to relax, order the heap by the lower bounds, and continue refining whichever interval is at the top of the heap until one has an upper bound below the lower bounds of all the others -- at that point, you can declare it the smallest. $\endgroup$ – j_random_hacker Apr 11 '19 at 17:47

Your Answer

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

Browse other questions tagged or ask your own question.