CODEWITHSUNDEEP
algorithmgraph
Epitheoritis 32
Epitheoritis 32

Reputation: 366

All minimum paths between the vertices of a graph

Let's say i have a directed graph G(V,E) with edge cost ∈ (0,1).For given i,I need to find all the couples of vertices (i,j) starting from i that "match".Two vertices (i,j) match if there is a directed path from i to j with length exactly k(k is a given number that is relatively small and could be considered as constant)with cost >=C(C is a given number).Cost of a path is calculated as the product of it's edges.For example if a path starting from i and ending in j of lenght 2 consists edges e1 and e2 then CostOfpath=cost(e1)*cost(e2).

I thought about finding all the paths of length exactly k and then check the cost of these paths to see if it is within the boundaries.However,i am not sure how to implement this idea(maybe with BFS or dijkstra)and i also think this is brute force so there is probably a more clever idea?

Upvotes: 0

Views: 134

Answers (1)

Yonlif
Yonlif

Reputation: 1790

First of all take a log for all of the costs in the graph, that way when you are summing them it will be like multiplying the weights (since log a + log b = log a * b). Then you will be able to use all the algorithms you know.

From here I can see two solutions:

  1. Find all pairs shortest paths, then take from them only the paths of length k. This will take O(V^3) for finding the paths.

  2. Use this question for finding all the paths of length k. You will need to find the time complexity by yourself.

You can iterate afterwards over the results and take only the ones with needed sum. This will take O(E)*O(V^2) the length of each path * the number of paths.
More logical option will be to remove paths you don't need during the process of the algorithm.

Don't forget to return the original length at the end.

Good Luck.

Upvotes: 1

Related Questions