Networkx with custom cost function for path

user_13401459 0
Viewed 45

I have the situation shown below where there is a weighted graph.

Graph

I am trying to get the best path from A to D based on a custom function, the total cost is the product of the previous costs.

  1. A - B - D = 0.6 * 30 = 18
  2. A - C - D = 0.3 * 40 = 12

I want to choose the second path (lower cost).

How can I do this using the networkx library?

thank you

networkx graph python
1 Answers

One way is to iterate over all paths and select the optimal one using a custom function. This is the rough (pseudo)code:

from networkx import all_simple_paths


paths = all_simple_paths(G, source, target)
costs = []
for p in paths:
    # obtain the edge weights and evaluate the cost using custom function
    cost = custom_function(p)
    costs.append((cost, p))

# sort the costs and pick the one with the smallest cost
lowest_cost, best_path = sorted(costs)[0]
user_106935960
Related