I already solved most the questions posted here, all but the longest path one. I've read the Wikipedia article about longest paths and it seems any easy problem if the graph was acyclic, which mine is not.
How do I solve the problem then? Brute force, by checking all possible paths? How do I even begin to do that?
I know it's going to take A LOT on a Graph with ~18000. But I just want to develop it anyway, cause it's required for the project and I'll just test it and show it to the instructor on a smaller scale graph where the execution time is just a second or two.
At least I did all tasks required and I have a running proof of concept that it works but there's no better way on cyclic graphs. But I don't have clue where to start checking all these paths...
The solution is to brute force it. You can do some optimizations to speed it up, some are trivial, some are very complicated. I doubt you can get it to work fast enough for 18 000 nodes on a desktop computer, and even if you can I have no idea how. Here's how the bruteforce works however.
Note: Dijkstra and any of the other shortest path algorithms will NOT work for this problem if you are interested in an exact answer.
Let's run it by hand on this graph:
1 - 2 (4), 1 - 3 (100), 2 - 3 (5), 3 - 5 (200), 3 - 4 (7), 4 - 5 (1000)
Here's how it would look iteratively (not tested, just a basic idea):
(*) - this is a bit of a problem - you have to keep a pointer to the next child for each node, since it can change between different iterations of the while loop and even reset itself (the pointer resets itself when you pop the
topStack.node
node off the stack, so make sure to reset it). This is easiest to implement on linked lists, however you should use eitherint[]
lists orvector<int>
lists, so as to be able to store the pointers and have random access, because you will need it. You can keep for examplenext[i] = next child of node i in its adjacency list
and update that accordingly. You might have some edge cases and might need to differentend:
situations: a normal one and one that happens when you visit an already visited node, in which case the pointers don't need to be reset. Maybe move the visited condition before you decide to push something on the stack to avoid this.See why I said you shouldn't bother? :)