Context
This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights (e.g. $\tilde{w}_{ij} = - w_{ij}$) will result in cycles with negative sum, thus no minimum cost walk exists in $\tilde{G}$.
General question
How well can we approximate the maximum weight path between $i$ and $j$ in $G$, using the shortest path algorithm on a graph $\tilde{G}$ with transformed weights $\tilde{w}_{ij}$ ? In my case, one has $w_{ij}\in\mathbb{N}\setminus\{0\}$. The transformed weights $\tilde{w}_{ij}$ can be obtained using any function, but I assume a decreasing function $f$ is well adapted so that $w < w' \iff f(w) > f(w')$.
My approach
I am currently trying to use $f(w) = \dfrac{1}{w}$, in this context we have two important paths given a fixed path length $L$.
Denote a path $p = (i_0i_1, i_1i_2, i_2i_3, \dots i_{L-1}i_L$) with weights $W = (w^{(1)}, w^{(2)}, w^{(3)}, \dots, w^{(L)})$,
denote the maximum weight path of length $L$ by $p^*$ with weights $W^*$ achieving $$ W^* = \arg\max_W\{\mathtt{Cost}(W)\} = \arg\max_W \sum_{k=1}^L w^{(k)}$$ and the path $p_*$ achieving minimum transformed cost with weights $W_*$ $$ W_* = \arg\min_W \sum_{k=1}^L \tilde{w}^{(k)} = \arg\min_W \sum_{k=1}^L f(w^{(k)}) = \arg\min_W \sum_{k=1}^L \dfrac{1}{w^{(k)}}$$
Specific question
In this specific context, do we have the approximation $\mathtt{Cost}(W^*) \approx \mathtt{Cost}(W_*)$ ?
Or is it "very wrong" to replace $W^*$ by $W_*$ ? What would be the distribution of the relative error defined as $$E_r = \dfrac{\lvert\mathtt{Cost}(W^*) - \mathtt{Cost}(W_*)\rvert}{\mathtt{Cost}(W^*)}$$
Statistical analysis
I have tried a quick statistical analysis as follows:
- Letting $L\in\{3,4,5,6,7,8\}$
- sampling $w \sim \mathrm{Uniform}(1,w_{\max})$
- The value for $w_{\max}$ was also picked from the set $\{50, 100, 150, 200, 500\}$
- for each combination of $L,w_{\max}$ I computed $10^5$ values of $W^*, W_*$ using $10^3$ candidate weights $W_i$
The results:
- In $80.8\%$ of cases we have $\mathtt{Cost}(W^*) = \mathtt{Cost}(W_*)$ and even better $W^*=W_*$
- When computing the relative error $E_r$ one finds that $82.6\%$ of error values are less than $0.001$, $89.7\%$ less than $0.01$ and $99.9\%$ less than $0.1$
The histogram for $E_r > 0$ is as follows
