1
$\begingroup$

I have a graph with weights of the form $a \omega + b$ where $a,b \in \mathbb{Q}$ and $ \omega$ is an infinite value, that is, a value such that for any rational number $q$, $q \le \omega$. The ordering relation over $\mathbb{Q}$ is extended to these values by imposing that $a \omega + b \le a' \omega + b'$ if and only if $a < a'$ or $a = a'$ and $b \le b'$. Since Bellman-Ford needs an addition operation, I define the addition of two such values as $(a_1 \omega + b_1) + (a_2 \omega + b_2) = (a_1 + a_2) \omega + (b_1+b_2)$.

Would Bellman-Ford still work in this domain?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ As far as I can tell, the algorithm works in any ordered abelian group. This probably follows directly from its analysis, but here is a high-level argument that does not require understanding the inner workings of the algorithm: it unconditionally terminates in a finite number of steps ($O(|V|\cdot|E|)$ independent of the weights), hence only finitely many values from the group are involved in the computation. Take this finite set, and include in it the sums of all simple paths and cycles. There exists a partial embedding of this finite subset of the group into $\mathbb Z$ (this is another ... $\endgroup$
    – Emil Jeřábek
    Commented May 28 at 9:52
  • 4
    $\begingroup$ ... way of saying that all universal sentences valid in $(\mathbb Z,+,<)$ are valid in all ordered abelian groups). Thus, you can replace the weights with integer weights in such a way that both the computation of the algorithm and the correct shortest path is preserved. Since the algoeithm work for $\mathbb Z$, it must give the correct answer here as well. Actually, in your particular group, an easier direct way of constructing such a finite embedding is just to replace $\omega$ with a very large integer. $\endgroup$
    – Emil Jeřábek
    Commented May 28 at 9:55
  • $\begingroup$ @EmilJeřábek I deduce that the computation of the negatively weighted cycles is also doable in an ordered abelian group. Is that right? $\endgroup$
    – user1868607
    Commented May 28 at 11:25
  • $\begingroup$ Yes. I took that as an integral part of the algorithm. $\endgroup$
    – Emil Jeřábek
    Commented May 28 at 11:27
  • 1
    $\begingroup$ Simila to what @EmilJeřábek said: Can't you just take omega to be nM for M the maximal b-value in the input? $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented Oct 17 at 14:16

1 Answer 1

Reset to default
-4
$\begingroup$

Yes, since it is not uncommon to model the lack of an edge between any pair or subset of nodes/vertices as an edge with infinite cost.

An edge of zero cost is a "short-circuit", without resistance/impedance/cost.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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