I'm trying to apply the Lanchester square law: $remainingUnits = \sqrt{a^{2}-b^{2}} $ to graphs, more specifically, the shortest paths. The formula represents the number of remaining units after battle, where $a$ is the size of our army and $b$ is the size of an enemy army.
Let's say we have the following graph: https://i.stack.imgur.com/vM9xP.png (where edges represent an enemy strength guarding the city) and we want to conquer city $L$ from city $A$ and our initial strength is $100$. Any shortest path algorithm would normally choose the upper path, as the sum of it's weights is less than to bottom path, however, we can't conquer city $L$ when we take the upper path, since the our army would die trying to conquer city $J$ (before city $J$, we are left with $43$ units vs $44$ units guarding the city $J$.).
However, when we take the bottom path, our army will successfully conquer the city $L$. After conquering city $C$, we have $60$ units left, after conquering city $E$ we have 40 units left.. and we are left with 7 units when city $L$ is conquered.
Normally, this would a be computer science problem and would require me to write some algorithm, basically not for this stack exchange. But, I have a theory it's possible to calculate a value (relative to our strength and strengths of enemy armies), which if we will add to weights of all edges, any shortest-path algorithm would choose the correct path right away and without requiring to write any code. And that is more fit for this SE, rather than StackOverflow.
Could you help me find that number or disprove my theory?
Thanks
If rounding doesn't matter, just square all the weights. The path minimizing $w_1^2 + w_2^2 + \dots + w_k^2$ (if its edges have weights $w_1, w_2, \dots, w_k$) is the best path, since an army of $100$ will be left with $$\sqrt{100^2 - w_1^2 - w_2^2 - \dots - w_k^2}$$ soldiers after taking that path.
In your example, I think that the shortest path is actually the best, and that following the upper path leaves you with $\sqrt{168}$ soldiers - so what I'm assuming is going wrong is that (quite reasonably) you're assuming that when an army of $100$ faces an army of $14$, it is left not with approximately $99.0152$ soldiers but with $99$.
In this case, a direct transformation won't quite work, since you have to take your entire history into account to determine how the rounding will go.
But ordinary Dijkstra's algorithm - modified, of course, to use the square law - will continue to find the optimal path.
Here, at every step of the algorithm, we have labeled some subset of the cities with the maximum number of soldiers we can have remaining when we reach that city. (Initially, just the starting city is labeled with $100$.)
We consider all possible avenues of attack out of all those cities, pick the one that leaves us with those cities, and use it to label one more city with the maximum number of soldiers we could have left after we conquer it.
(This still works just like the ordinary proof of Dijkstra: if attacking city $X$ directly from the cities we understand leaves us with $k$ soldiers, and attacking any other city $X'$ leaves us with at most $k$ soldiers, we're not going to have another indirect route to $X$ that does any better than $k$.)