Jump to content
  • Advertisement
Sign in to follow this  
Zoomby

I'm searching a graph algorithm

This topic is 4928 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

Advertisement
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.


I'm not sure if you even know what you want. The shortest path from node A to any node is the same as the shortest path from any node to A. This is assuming you are using a simple graph.

How about you specifically state the type of graph you are working with?

Share this post


Link to post
Share on other sites
Quote:
Original post by Zoomby
@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?


As you can see in animation of the dijkstra algorithm, it builds a shortest-path spanning tree. If I undestand you correctly, this means that it builds precisely what you need in one iteration. A tree containing the shortest paths from a root (A) to all the other nodes in the tree.

Tom

Share this post


Link to post
Share on other sites
If it is not weighted, then you don't need to use dijkstra (aka uniform cost). Just use iterative deepening.

Share this post


Link to post
Share on other sites
@dimebolt

As I said before, if I use Dijkstra I can find the shortest path from root (A) to all the other nodes, but not from any node to A. This is because I can't go back in my graph.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zoomby
@dimebolt

As I said before, if I use Dijkstra I can find the shortest path from root (A) to all the other nodes, but not from any node to A. This is because I can't go back in my graph.


Can't you just reverse the direction of the edges while running the algorithm?
Or am I overlooking something?

Tom

Share this post


Link to post
Share on other sites
Quote:
Original post by Zoomby
@dimebolt
No, you are not allowed to go back in the graph I use.


I understand. I should have stressed the 'while'. What I meant is this:
graph:
A->B->C->A

shortest route from B to A = B->C->A
shortest route from C to A = C->A

Running iterative deepning from A on this graph will fail, as you mentioned (because it will yield A->B and A->B->C which do not exist in the backward direction).

However, if we revert the direction of all edges during the algorithm:
A<-B<-C<-A
Running iterative deepning from A on this graph will yield A<-C and A<-C<-B, which are the proper routes (if you read them from right to left).

But, as I said, maybe I overlook something.

Tom

EDIT: fixed some stuff...

[Edited by - dimebolt on August 26, 2005 8:08:03 AM]

Share this post


Link to post
Share on other sites
Zoomby, those paths to node A from all other nodes would be unique, so you would have to basically search for the path from each of those nodes to A and store them somewhere. Since the edges are not weighted, you do not need to use dijkstra's. Just use iterative deepening. Dijkstra on an unweighted graph is worse than just plain old breadth-first.

Ok, so is this graph you are working with also a directed multi-graph? If so, then it might be a good idea to do some research, because I'm sure there are certain things that could be employed to reduce the number of nodes that need to be searched. One case would be where A is connected to B and B is connected to A. In such a case where you perhaps had lists of unknown paths for each node, you could add the path A -> B and B -> A for each respective node which would reduce the number of searches you have to do by one. Another case I can think of that would be similar would be loops.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!