CODEWITHSUNDEEP
pythonnetworkxgraph-theory
lhoupert
lhoupert

Reputation: 704

Calculate shortest path in networkx using edge cost function

I would like to use networkx to calculate energy-efficient routes. To do that I thought about modelling battery constraints as edge cost functions. In the example below, I would like to calculate the shortest route between s and t depending of the battery load of my vehicle (b). The constraints of my network will determine the edge cost function.

For example between s and v1, the edge cost will be 18 if the battery load at s is superior to 18 or (close to infinite) if it is less than 18.

Is it possible to define edge cost functions that will be used by shortest path algorithms in networkx?

example

Or do you think the best solution would be to create a new MultiDiGraph where all the different possible edge costs are recalculated according to the initial charge at the starting point?

Edit 1: To simplify the problem we can consider the negative weights (corresponding to a recharge of the battery) as equal to zero. In a second time, I will see how to use Johnson's algorithm. It seems to be implemented in networkx (https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.johnson.html)

Edit 2: The maximal battery load is 20 which explains why the battery load didn't increase between s and v_3 and why it is impossible to reach t through s->v3->v2

Upvotes: 0

Views: 760

Answers (1)

ravenspoint
ravenspoint

Reputation: 20457

  1. Assume an initial battery level infinity.
  2. Search the resulting calculated costs for the most negative.
  3. Add absolute value of most negative cost ( X ) to cost of every link.
  4. Run Dijsktra's algorithm to find lowest cost from source to distance.
  5. Subtract X from path cost ( P - X )
  6. If initial battery level greater than ( P - X ) then destination is reachable.

For example

C:\Users\James\code\PathFinder\bin>gui
l s v1 38
l s v3 0
l v1 v2 0
l v3 v2 38
l v2 t 23
s s
e t

s -> v3 -> v2 -> t ->

( PathFinder is a C++ wrapper for the boost::graph impementation of Dijsktra )

So, now we have a new previously hidden constraint that the battery capacity has a maximum of 20. So I propose another aproach which should be proof against any further constraints that might pop up. It is based on the ideas of the A* algorithm

  1. Reformulate the problem so that the recharging stations are at nodes and the links betwen the recharging stations have constant positive costs. ( This seems to me a more natural model of the real world )

  2. Use Dijsktra, considering only link costs, to find the cheapest path to the destination from every node connected to the current done ( initially the starting node )

  3. For every node connected to the current, sum the cost of the link from the current, the cost to the destination calculated in 1 minus any recharging that the node offers.

  4. From every node that has been costed in 3, choose the cheapest. Keep track of the path used to reach this node and make it the current.

  5. Repeat from step 2 until the destination node is reached.

This is a very specialised problem, ao I will not be adding it to the PathFinder options. If it represents a serious real world problem, not just homework or an acedemic exerise, open a issue on the PathFinder github repository and we can discuss details of developing a one-off application for this.

Upvotes: 1

Related Questions