Thread: Shortest path problem for undirected graph, with no weights per edge

1. Yeah, out of curiousity, what's this graph being used for? Is this your polytope thing from before

2. Originally Posted by MutantJohn
Yeah, out of curiousity, what's this graph being used for? Is this your polytope thing from before
Not in the mood for reading the first half of this thread?

3. Uh... I don't think it said anything about what the graph represented, did it? It just seemed like it was about the best way to handle large graphs and then the conversation turned to, "Well, there are two algorithms depending on the nature of the graph." You'll have to excuse me if I find creating a large graph arbitrarily for the sake of traversing it to be rather... I want to say boring but I don't want to mean it. It holds little interest for me and I was wondering if there were any big plans behind it.

4. Originally Posted by MutantJohn
Uh... I don't think it said anything about what the graph represented, did it? It just seemed like it was about the best way to handle large graphs and then the conversation turned to, "Well, there are two algorithms depending on the nature of the graph." You'll have to excuse me if I find creating a large graph arbitrarily for the sake of traversing it to be rather... I want to say boring but I don't want to mean it. It holds little interest for me and I was wondering if there were any big plans behind it.
Gah! After my post, did you go back and re-read the entire first half of this thread carefully? The first post didn't mention what it's for, but post #8 just might have. Besides, finding the shortest path from one node to another is not "arbitrary traversal". Regardless of the specific application, there are many interesting use cases you could imagine std10093 using it for (or, if you didn't know anything about it, and thus couldn't imagine, you could have read the links I posted to learn about it's applications): network routing, robotics/path finding, transportation, puzzles solving, video games, etc. No need to apologize though, I don't blame you for finding pointless traversals boring and, well, pointless; just for not reading carefully .

5. You're totally right. Sorry, I walked in to this like half-way and only skimmed. I was assuming it'd stand out more but such are the lessons we learn...

6. Since your graph models a social network, you can find nice heuristics to (possibly) increase your speed by orders of magnitude.
Assume for example, that you need to find the closest relation between two people..
(So..If (A,B),(B,C),(C,D) are friends, A and D have two in between.)
Now, instead of plain BFS, if you consider the people in the same geographical area first when putting nodes into your queue, it is likely that you'll have a solution (or one very close to it) very quickly.

Only when you have tried the standard algorithms and figured that you need a faster solution, should you try these.
The more clever your heuristic function is, better/faster the results you can count on.

7. I will think that for later. tnx