Solve a simple system of linear inequalities in natural numbers I want to find a solution to a system of linear inequalities of the following form

\begin{aligned}
a_1 + b &amp;\ge a_2 \\\
\vdots \\\
a_4 + c &amp;\ge a_1
\end{aligned}

where $a_i \in \mathbb N \setminus \{0\}$ and $b,c \in \mathbb Z$. All inequalities consist of exactly two variables and one free factor. All $a_i$ appear as they are, and have no coefficient other than $1$.

The goal is to find a solution (perhaps more than one, but not necessarily), or declare the system as not having one. Such a solution would be vastly preferable to any linear programming ones.

I do remember some algorithm based on constructing a graph and then launching Floyd-Warshall algorithm could solve a similar problem, but I'm not sure.



EDIT: Problem expansion - how can I find such a solution that the number of distinct integers in the solution is maximized (the default Bellman-Ford behavior minimizes it)
Construct a graph with one vertex per variable, and one extra vertex $s$. Make an edge from $s$ to all other vertices, of length zero. For each inequality $a_i + c \ge a_j$, make an edge of length $c$ from $a_i$ to $a_j$. Then if your graph has a negative-length cycle, your inequalities have no solution, and if it does not have a negative-length cycle then the distance from $s$ to each vertex gives a solution. You can use Floyd or Bellman–Ford or any other shortest path algorithm that can allow negative weights.