Also, it sounds like the way you want to store your nodes is in an adjacency matrix/list. Or maybe, some partial version of that, only concerned with nodes that are close to the current node.
One more good reference, to help get you using the right language: Glossary of graph theory - Wikipedia, the free encyclopedia.
Note, if time is of little concern, but space is, you can use DFS to exhaustively search every possible path.
Why prefer DFS over BFS?Originally Posted by anduril462
The goal is the time. The faster, the better!
As for the algorithms, I think that I should avoid those that have E in their time complexity and only check the ones left and find the "optimal" from them (the ones that have only V inside them).
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
I'd query that too, without knowing more about the specific problem. Each has tradeoffs.
I'd look a bit more carefully than that. Some of the algorithm with complexity only in terms of V have higher powers (for example, because the number of edges is a more-than-linear function of number of vertices).
Didn't I state the specific problem? What more should I state?
What do you mean by "higher powers"? Probably I am lost in the language here. Also the example is not clear to me too. Sorry :/
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
You made no mention of runtime needs, yet did mention that the size of the graph was large, and that it may exceed memory. That, combined with your "background" paragraph -- particularly the part about now wanting to hold the entire graph in memory -- led me to believe you were more concerned with memory than speed, which you didn't mention at all. Note, most people optimize for time nowadays, but optimizing for space is still something that people do.
Given that grumpy found it unclear, and I misunderstood what you were getting at, it may be underspecified. Now we know you're optimizing for speed. But we don't know how much bigger |E| is than |V|.
By higher power, grumpy means "order" or "exponent". What grumpy is saying is that, you may find an algorithm where there is only |V| in the time complexity, but it may still be slower than one with |V| and |E|, even if |E| > |V|. For example, assume |V| is large (millions of nodes) and |E| is on the order of 100 |V|.
Now, imagine you have two algorithms, one with just |V| in the time complexity:
O(|V|3)
and another with both |E| and |V| in it
O(|E| * |V|)
Which is faster in this case? The second one. The better algorithm will depend on just how much bigger |E| is than |V|. In the above, as long as |E| < |V|2 (which I think it must be -- you cannot have |V|2 edges in an undirected graph), the second algorithm is faster. This is one area where you could have specified better: just how big is |V| and how much bigger is |E| than |V|?
