Dynamic costs in pgr_bellmanFord

[Kmortyk]

Hello,

I am trying to find the most profitable paths in the Ethereum blockchain. My graph represents tokens between which transfers are possible.

I would like to ask if it is possible to use dynamic costs in methods such as pgr_bellmanFord? By dynamic costs, I mean modifying the cost of an edge as the algorithm passes through the graph based on previously added edges in the path.

Am I correct in understanding that this is the problem of finding paths in time-dependent graphs? I am unsure because in my case, it is possible for the weight to decrease as the algorithm travels along the edges.

Thank you very much.

[TimMcCauley]

You can update the edge costs after the algorithm has conducted the shortest path computation. I have typically done this in an pgpgsql script looping over a set of source and targets.

I would move this to discussions as it makes more sense there.

[Kmortyk]

Thank you for your reply.

I now understand that weights cannot be updated while the algorithm is running. In my particular case, I would like this to happen during pathfinding.

I have updated the discussion category to "General." Please let me know if this is incorrect.

[TimMcCauley]

Thanks. Could you provide a basic example how you imagine this to work? Do you have negative edge weights in your example or why would you like to use Bellman Ford?

[Kmortyk]

I want to search for the most profitable path in my graph. Each forward cost on edge $i$ is defined by the function $f_{i1}$ and the reverse cost by $f_{i2}$.

For example, in the picture, the most profitable path from A to D goes through node B in my graph. The algorithm could compare the edges by how much we get at the output of the cost function.

I was thinking of using the Bellman-Ford algorithm since it supports negative costs. I could make all the costs negative and try to find the shortest path in the graph with it.

However, the Bellman-Ford algorithm works with fixed cost values in pgRouting (https://docs.pgrouting.org/latest/en/pgr_bellmanFord.html).

It would be useful for me to be able to pass the current output value at each step of the algorithm for calculating the actual cost.

[TimMcCauley]

Thanks for your explanation. Could you instead use Dijkstra on your directed graph and loop over all combinations? Dijkstra has the advantage of visiting every vertex just once. Then you could update the costs after each iteration?

[TimMcCauley]

Maybe this approach could help you: https://docs.pgrouting.org/3.1/en/pgRouting-concepts.html#one-to-many you can iteratively loop over all source vertices, for each iteration grab the resulting paths and update the visited edges accordingly before moving forward.