CODEWITHSUNDEEP
algorithmgraph-theory
william007
william007

Reputation: 18535

Random walk for find the path with higher cost

I have a acyclic directed graph with a start vertice and an end vertice and some unknown number of vertices in between. A path starts from start vertice and end at end vertice. It is known that the number of vertices along the any paths between the start vertice and end vertice <100, but the number of possible vertices could be very large. Each vertice has a cost assigned to it, and the cost of the path is summation of the cost of vertices in between. Is there a way to use the random walk or any other means (this is to avoid explore all the vertices) to find for the path that has the highest (or near-highest) cost?

Upvotes: 1

Views: 414

Answers (1)

Konsol Labapen
Konsol Labapen

Reputation: 2434

This problem is solved on Geekviewpoint.com with detailed explanation. It augments Dijkstra's algorithm. http://www.geekviewpoint.com/java/graph/dijkstra_constrained

EDIT: to account for 100 vertices between each path.

Originally your problem said there were 100 paths between the start and finish vertices. But by your correction, it's actually 100 vertices on the path. In that case your optimization is straightforward using DFS.

As you try to assemble a path, track the number of vertices you have seen. If the number reaches 99 and does not link start to finish, abort that path and try another one unit you get the answer if it exists. The algorithm you need to modify is DFS for cycle detection. Any algorithm textbook will have one of those. Since you also need to pick the best path among those found, you should also look at http://www.geekviewpoint.com/java/graph/count_paths.

I don't know if I should tell you how to do the obvious, but you will track the past path you have found similar to how you would find the maximum element in an array. The code is not difficult, you just have to combine a few small ideas:

  • DFS (similar to cycle detection and similar to counting paths, the two overlap)

  • track the best path you have seen: a one entry map where the idea is map which you keep replacing if you find a shorter path.

Upvotes: 2

Related Questions