0

Hi everyone,

I've been working on this for days, but just can't get it. I have a linked-list containing edges of a weighted directed graph, and my goal is to find a path from vertex A to vertex B going through exactly n nodes. Anyone has suggestions, or links with examples? Thank you!!!

2
Contributors
2
Replies
5
Views
10 Years
Discussion Span
Last Post by DynamitMsk
0

Hi everyone,

I've been working on this for days, but just can't get it. I have a linked-list containing edges of a weighted directed graph, and my goal is to find a path from vertex A to vertex B going through exactly n nodes. Anyone has suggestions, or links with examples? Thank you!!!

Since you have worked for days on it, you must have done some research or some coding. Let us know about it.

0

I'm thinking of using something like BFS, that would just go out and label nodes by degree of closeness to given node, but thats not too efficient, I've also tried Dijkstra approach, because my other priority is to minimize that path in terms of length, but I don't think I can use it. My current plan is to use greedy approach starting at node A and go to a node n-1 far from it, then seeing if that node is directly connected to B. If it is - good, but if not then I'd have to roll back to n-2, and try to go to B from there via another node. If that fails, roll back to n-3...etc. Should I use recursion for this approach?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.