CODEWITHSUNDEEP
javagraphgraph-algorithmshortest-path
user219882
user219882

Reputation: 15834

How to find the best path in graph with weighted nodes and vertices

Let's say I have this graph

example graph

I want to find a path short as possible but with the best score (sum of points of nodes) - in other words a path that can't be longer then some defined constant but give me the best amount of points. And I want to start and stop in the same node and don't want to go over already visited nodes.

Are there any algorithms which could help me with this problem or do you have any ideas how to solve it?

Oh, and it's not a homework, I just want to create a special path finder.

EDIT

So far I've been able to construct a working algorithm which can find some path in a few seconds. But I don't get the amount of points I'd like to - I get only about 85% of the desired score. And if I change the algoritm's parameters then time will be in hours and more...

Upvotes: 0

Views: 2773

Answers (2)

adelbertc
adelbertc

Reputation: 7320

I'm not sure if this would actually work, but these are my initial thoughts:

Perhaps try with the maximum spanning tree (Prim's or Kruskal's). Since you don't want to repeat vertices, your path must end up being the cycle graph. Walk the spanning tree (maybe some sort of greedy algorithm?) and once you hit a leaf, go back to the start vertex (since the original graph was the complete graph). This would only work (maybe) if there were no negative edge weights.

Just some thoughts for now - it's late at night, I'll take a closer look in the morning. :)

Upvotes: 0

FrankieTheKneeMan
FrankieTheKneeMan

Reputation: 6800

I don't think this is solvable in better than brute force time. You could calculate all paths up to a certain constraint length. However, for an arbitrarily large graph that would be extremely slow. If you're looking for a solid guess, I'd start with a greedy algorithm that picks the step with the highest Points per Length value, until the limit is reached. You can then add things such as reversing in the case of premature filling (say, if you've gone 5, but your limit is 6, and your current node has no paths of length one connected) to find out how that works.

Upvotes: 1

Related Questions