CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
Martin Thurau
Martin Thurau

Reputation: 7644

Graph search with weight limit

I have a undirected, weighted graph with objects of an arbitrary type as nodes. The weight of an edge between two nodes A and B is the similarity of these two nodes in the interval (0, 1]. A similarity of 0 leads to no connection between to nodes, so the graph may be partitioned.

Given a target weight w and a start-node S, which is an algorithm to find all nodes that have a weight > w. Subnodes (seen from S) should have the product of all weights on the path. I.e:

S --(0.9)-- N1 --(0.9)-- N2 --(0.6) -- N3

Starting with S the nodes will have the following similarity values:

N1: 0.9 
N2: 0.9 * 0.9 = 0.81
N3: 0.9 * 0.9 * 0.6 = 0.486

So given S and the target weight 0.5 the search should return N1 and N3. Wheres a search starting from N2 would return S, N1 and N3.

Are their any algorithms that fit my needs?

Upvotes: 2

Views: 628

Answers (2)

amit
amit

Reputation: 178441

note the following:

  1. log(p1 * p2) = log(p1) + log(p2)
  2. if p1 < p2 then log(p1) < log(p2) and thus: -log(p1) > -log(p2)

Claim [based on the 1,2 mentioned above]: finding the most similar route from s to t, is actually finding the minimum path from s to t, where weights are -log of original.

I suggest the following algorithm, based on Dijkstra's algorithm and the above claim.

1. define for each edge e: w'(e) = -log(w(e)) //well defined because w(e) > 0
2. run Dijkstra's algorithm on the graph with the modified weights.
3. return all vertices v that their weight is dijkstra(v) < -log(needed)

Upvotes: 5

penelope
penelope

Reputation: 8418

You could try using the Bellman-Ford algorithm, since it's working fine with both summation and multiplication of edges, as well as with minimums and maximums (you calculate the longest paths -- use the maximum -- by doing the inverted operation).

Also, if you take a logarithm of all your paths, the problem then reduces from multiplication to summation. After that, you could reverse the signs of the weights (to turn the problem from finding a minimum to finding the maximum) and use the Bellman-Ford algorithm on that graph. Since all your weights are initially between 0 and 1, after both of these transformations you should probably be able to use Dijkstra as well.

Then after calculating the paths, just revert the transformations back and check which "distances" suit you.

Upvotes: 0

Related Questions