<p>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.</p>
<p>An edge of zero cost is a &quot;short-circuit&quot;, without resistance/impedance/cost.</p>

CC BY-SA 4.0
2024-10-17T11:30:12.510Z
2024-10-17T11:30:12.510Z
Giovanni
<p>I have a graph with weights of the form <span class="math-container">$a \omega + b$</span> where <span class="math-container">$a,b \in \mathbb{Q}$</span> and <span class="math-container">$ \omega$</span> is an infinite value, that is, a value such that for any rational number <span class="math-container">$q$</span>, <span class="math-container">$q \le \omega$</span>. The ordering relation over <span class="math-container">$\mathbb{Q}$</span> is extended to these values by imposing that <span class="math-container">$a \omega + b \le a' \omega + b'$</span> if and only if <span class="math-container">$a &lt; a'$</span> or <span class="math-container">$a = a'$</span> and <span class="math-container">$b \le b'$</span>. Since Bellman-Ford needs an addition operation, I define the addition of two such values as <span class="math-container">$(a_1 \omega + b_1) + (a_2 \omega + b_2) = (a_1 + a_2) \omega + (b_1+b_2)$</span>.</p>
<p>Would Bellman-Ford still work in this domain?</p>

CC BY-SA 4.0
2024-05-28T09:52:51.727Z
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 ...
Emil Jeřábek
CC BY-SA 4.0
2024-05-28T09:55:05.960Z
... 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.
Emil Jeřábek
CC BY-SA 4.0
2024-05-28T11:25:51.163Z
@EmilJeřábek I deduce that the computation of the negatively weighted cycles is also doable in an ordered abelian group. Is that right?
user1868607
CC BY-SA 4.0
2024-05-28T11:27:34.047Z
Yes. I took that as an integral part of the algorithm.
Emil Jeřábek
CC BY-SA 4.0
2024-05-31T00:39:19.703Z
search for [lexicographic max flow](https://www.google.com/search?client=safari&rls=en&q=lexicographic+max+flow&ie=UTF-8&oe=UTF-8)
Neal Young
CC BY-SA 4.0
2024-10-17T14:16:20.723Z
Simila to what @EmilJeřábek said: Can't you just take omega to be nM for M the maximal b-value in the input?
Antoine Amarilli 'a3nm'
<ds.algorithms><shortest-path>
Bellman-Ford with infinite weights
user1868607
# Bellman-Ford with infinite weights

(Asked by: username_0 on 2024-05-28)

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?

**Tags:** ds.algorithms, shortest-path

> **Comments:**
> **username_1**: 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 ...  
> **username_1**: ... 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.  
> **username_0**: @EmilJeřábek I deduce that the computation of the negatively weighted cycles is also doable in an ordered abelian group. Is that right?  
> **username_1**: Yes. I took that as an integral part of the algorithm.  
> **username_2**: search for [lexicographic max flow](https://www.google.com/search?client=safari&rls=en&q=lexicographic+max+flow&ie=UTF-8&oe=UTF-8)  
> **username_3**: Simila to what @EmilJeřábek said: Can't you just take omega to be nM for M the maximal b-value in the input?  

---

## 1 answers

### Answer by username_4 on 2024-10-17. Score: -4

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.


---

