Finding path in a graph using linked list
 

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!!!

Re: Finding path in a graph using linked list
 

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

Re: Finding path in a graph using linked list
 

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?