CODEWITHSUNDEEP
pythongraphtraversal
Simrayz
Simrayz

Reputation: 23

Find path in graph with weighted vertices

I have the following graph, where each vertex has an associated "probability" (graph with weighted nodes).

Weighted, undirected graph

I want to find the path from node 0 to the last node (highest index, here 5), which has the highest multiplied probability. In this graph, the best path is 0-1-4-5, which gives 0.72 probability.

I've thought about using BFS to find all paths between the start and end node, and then multiplying the probability for each node, but I think it's too näive of an approach to work for all graphs. How could I solve this using python?

Upvotes: 0

Views: 2335

Answers (1)

James
James

Reputation: 1238

As Julien suggested, Dijkstra's algorithm would be a good start here. There are two differences between your problem and normal Dijkstra's.

  1. Dijkstra's algorithm minimizes the sum of weights. To maximize the product of probabilities, you can map each weight p to -log(p). Quick proof: maximizing the product of (x1*x2*...*xn) is the same as maximizing log(x1*x2*...*xn) since log is monotonically increasing. argmax(log(x1*x2*...*xn)) = argmax(log(x1)+log(x2)+...+log(xn)) = argmin(-log(x1)-log(x2)-...-log(xn))). Note that if you want the resulting probability, you would invert your result by taking 10^(-c) where c is the minimum cost as returned by Dijkstra's using the above reduction (assuming you took the log with base 10). Note also that if any probabilities are 0, log(0) is undefined, so you should handle this by making the weight infinite (so a path would never go through that node).

  2. Dijkstra's uses weighed edges, whereas you have weighted nodes. But it is a simple reduction from weighted nodes to weighted edges. Define the weight of an edge from u to v with edge_weight(u,v) = vertex_weight(v). Judging by your picture, you have an undirected graph, so you would need to replace each undirected edge with two directed edges, using the same weights as described above (note that the two edges between two vertices u and v will have different weights, unless vertex_weight(u) == vertex_weight(v)). Also, if you want to return the value of the shortest path, you will need to add vertex_weight(source_vertex) to the final cost, since this cost is skipped in the reduction.

Upvotes: 3

Related Questions