Elysian Shadows

Your program IS the sentinel that is probing the links: a) they store a value something like person X - person X (next hop, person in question) b) each friends lets all its friends know that someone is looking for person X, and you can get him through me. c) those friends store in same format (jack ...

my original spec said that you had to produce the path. i mean its worthless information if you dont know what the connection is. Looks like I missed that, need to rethink the solution. secondly. its not traversal !!! you need a sentinel to make it traversal. It is a breadth first traversal . You g...

As long as the original problem is only to find if a connection exists rather then finding the actual path (hence my earlier questions), we can get away with just storing the island Id per person (an int). Your solution is still a traversal as the point of the execution is traversing through the nod...

After talking with a friend, we have a solution that has a complexity of O(1) for lookup if there is a connection between two people and a worse case complexity of O(n * 0.5) where n is the number of nodes in the network to add a friend. The overall cost is better then any graph traversal where the ...

I may have miss-understood your algorithm, are you doing breadth first or depth first? At the moment, I am assuming you are going from the target, iterating/traversing through its friends list and then iterating/traversing through the friend's friends list, etc.

Isn't that just breadth first graph traversal starting from the end point?

Hm. An alternative solution is to cache all possible connections as friends are added to each person. Disadvantages is that it requires more memory and the performance hit on added friends but the search time is dramatically reduced. Whether this is better then doing the search each time really does...

As long as you are looking for a relative distance rather then exact, you can remove the sqrt by doing what avansc said which makes the algorithm much faster.

Hm. As a starting point, I am currently thinking along the lines of a breadth first graph traversal and making nodes as 'dirty' so I don't traverse through the same nodes twice. Unfortunately, it is still pretty brute force.

IIRC, a logical language like Prolog would probably be best for this type of question. Shame I can't remember any of it :/

Added question, is it assumed that if A is friends with B, then B is friends with A?

Is there an upper limit to how many friends can you have?
Do we know what is the average number of friends one person has?
What is the maximum number of links a person can have before a connection is deemed invalid?
What is the target language?

i still remain that if you use malloc(n) and not malloc(sizeof(n)) you would be considered not only a sub par programmer but a dangerous one at that. and its not my opinion, its fact. and its not PORTABLE!!! Actually, whether it is portable or not depends on the context where malloc is used. You ar...

For simplicity, this is done in one source file. I assume you know enough C++ to split this into separate files: (WARNING: massive code dump) // Forward declarations class IController; //-------------------------------------------------------------- class Actor { public: Actor(); virtual ~Actor(); v...

bugmenot, does that still bug you? Better. Remember you are dealing with beginners most of the time so solving problems that don't exist yet for them is more likely to hinder/confuse them unless you provide them with an explanation. So posting the previous post first and then going "Oh, here a...