Jump to content
  • Advertisement
Sign in to follow this  
Zoomby

I'm searching a graph algorithm

This topic is 4828 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, what is the best algorithm to find the value "how many nodes (steps) away is a specific node (the smallest possible number of steps)" for each edge of a graph? This specific node is known before the algorithm. I would use a breath-first to find the nodes. And then for each found node use another depth-first to find the shortest way to the specified node. But maybe there's a better way. Bye Chris

Share this post


Link to post
Share on other sites
Advertisement
Hi,

I would really like to help you, but I don't seem to get what you want to do.

Okay, I hope I got it right.

Why don't you make a breath-first from the specified node and mark on each other node who far you went.
Eachtime you visit a node (since it's a graph you check if the node was visited or not) and if it was not visited set the current distance.

Share this post


Link to post
Share on other sites
@dragongame
I think this would only tell me how much steps behind the specific node is. I want to know the number of steps to the specific node, if I go foreward.

Ciao
Chris

Share this post


Link to post
Share on other sites
@C0D1F1ED
This would'nt work either I think. Dijkstra tells me the shortest path from node A to any node. But I want to know the shortest path from any node to A. It's the reverse problem.

Share this post


Link to post
Share on other sites
Ok,

so you have a directed graph?
If so you could still use my allgo by just inverting the direction.
because then all nodes that are just 1 step away from the special node will get a 1 and all nodes that are 2 steps away will get a 2 and so on ...
you could even save the path as a stack

EDIT:

just read the post above (I'm too slow :-)

Share this post


Link to post
Share on other sites
Since I'm assuming this is just a simple graph, I would say that the best thing to use would be iterative-deepening search. An iterative-deepening search is a depth-limited search that increases the max search depth by one until the goal node is found or no new nodes are searched. It is faster and less memory intensive than breadth-first, and it is more reliable than depth-first search.

Unfortunately, you haven't defined the problem well enough that I could give a specific implementation that would be the fastest for your needs. If you need to know the node distance of every node from the starting node or the graph is static, then it would probably be good to maintain some sort of structure with that information in it. If the graph is not static and you do not need to know the node distance of every node from the starting node, then you would need to run the search each time, get the path, and note how many nodes are contained in that path. Knowing what type of graph this will be used on would be very helpful too.

This is just from general CS knowledge though. If you need the supreme best method devised to this date for your specific problem, then you will probably need to do some research.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zoomby
@C0D1F1ED
This would'nt work either I think. Dijkstra tells me the shortest path from node A to any node. But I want to know the shortest path from any node to A. It's the reverse problem.

If it is true that for every node k, the adjacent nodes of k are also adjacent to k and have equal cost (an equal-cost path exists in both directions), then Dijkstra's algorithm works. If not, you'll need to be more specific about your situation.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zoomby
@C0D1F1ED
This would'nt work either I think. Dijkstra tells me the shortest path from node A to any node. But I want to know the shortest path from any node to A. It's the reverse problem.


This statement is very confusing. What do you mean with 'any node'? Clearly you do not mean an arbitrary node B, because Dijkstra would work for that.

Tom

EDIT: wow, beaten by like 5 posts. I most be the slowest guy on earth :)

Share this post


Link to post
Share on other sites
@dragongame
So I have to use a Dijkstra or other shortest-path algorithm with every node? Then the whole algorithm would be nested breath-firsts (one breath-first to find each node, and another Dijkstra breath-first for each found node) as I described first. Is there a way to do it using only one pass?

Ok, I'll try to draw the problem :)

Consider this graph:
A -> B
B -> C, A, B
C -> A

Each edge has a variable which should tell the number of steps to, say A.

So after the alogrithm the graph should look like this:
A -> B(2)
B -> C(2), A(1), B(2)
C -> A(1)

The numbers tells for example: I am currently visiting node B, if I choose edge C I have to do 2 further steps to come back to A.







Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!