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

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?