I’m using the Bellman-Ford algorithm to find the best path in my graph. However, instead of choosing the path with the lower value, I want to choose the path with the highest value. And instead of using the sum of all edges as a length of a path, I want to use the following formula: `lengthOfPath = sqrt(a^2 - b^2)`

for each edge, where `a`

is the edge we are coming from, and `b`

is the edge we are arriving to.

Basically, the formula represents the number of units left in our army after conquering a city, so logically, we want to choose the path with the least casualties.

My idea was to use the Bellman-Ford algorithm and rewrite the relaxation so it works according to our rules. I’m using a custom library for graphs and I already created a graph `g`

, added all cities as vertices and set the weight of an edge between `a`

& `b`

is the size of our military, while the weight of an edge between `b`

& `a`

is the size of enemy military guarding the city, where `a`

& `b`

are our vertices (cities).

I used the following code (`g`

is our graph, `getVertices()`

and `getEdges()`

returns a set of all vertices and edges, `getSource()`

and `getTarget()`

returns a source or target vertex of an edge etc..):

`public Map<Vertex, Double> bellmanFord(Vertex s) { Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY); d.put(s, 0d); for (int i = 0; i < g.getVertices().size(); i++) for (Edge e : g.getEdges()) relax(e, d); return d; } public void relax(Edge e, Map<Vertex, Double> d) { Vertex u = e.getSource(); Vertex v = e.getTarget(); if (d.get(u) + e.getWeight() < d.get(v)) d.put(v, d.get(u) + e.getWeight()); } `

And below is my modified code for the relaxation:

`public void relax(Edge e, Map<Vertex, Double> d) { Vertex u = e.getSource(); Vertex v = e.getTarget(); if (d.get(u) - formula(g.getEdge(u, v).getWeight(), g.getEdge(v, u).getWeight()) > d.get(v)) d.put(v, d.get(u) - formula(g.getEdge(u, v).getWeight(), g.getEdge(v, u).getWeight())); } public double formula(double ourCity, double enemyCity) { double a = Math.pow(ourCity, 2); double b = Math.pow(enemyCity, 2); double result = a - b; return Math.sqrt(vysledok); } `

However, using my modified code for relaxation the Bellman-Ford is not working correctly. It always returns a map with all values set to infinite. Could you help me fix my problem?

Thanks