Jump to content
  • Advertisement
Sign in to follow this  
Zoomby

I'm searching a graph algorithm

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

Quote:
Original post by dimebolt
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 dijkstra 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 dijkstra from A on this graph will yield A<-C and A<-C<-B.
If we undo the reversion: A->C and A->C->B, which are the proper routes.

But, as I said, maybe I overlook something.

Tom



Dude, the graph isn't weighted. He shouldn't be using dijkstra.

Share this post


Link to post
Share on other sites
Advertisement
@dimebolt
The paths A->C and A->C->B are not legal in my graph. The edges are all uni-directional.

@Zefrieg

So, I have to do MULTIPLE searches from each node, and one pass over the nodes will never be enough? Then the remaining problem would be to optimize these multiple searches

Share this post


Link to post
Share on other sites
Quote:
Original post by Zefrieg
Dude, the graph isn't weighted. He shouldn't be using dijkstra.

Fair enough. But replace Dijkstra by iterative deepning from A and my trick still works...

Tom

Share this post


Link to post
Share on other sites
Ok,

for you are not allowed to revers the order for the time the allgo runs and you can not copy the graph and revers the order in the copy.

Then I would do the following:
Make a list of all nodes which don't have a number yet.
Select one (randomly or just the first of the list)
Make iterated deepening from that node until you found the "special node".
Rememerber the way and its length go from the start node and set the value of the node to the length. Then go the way and set the the correct values.

Then select the next node without a value and do the same.
But as soon as you hit one with a value you can abort the allgo since you know now the rest length.

Share this post


Link to post
Share on other sites
I doubt anyone around here knows the best way to find all the shortest path trees for each node in a unweighted directed graph. Though, I'm sure you could find papers on better methods to solve this problem.

Be sure to look for those papers before trying to create a better way yourself. No reason to reinvent the wheel.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zoomby
@dimebolt
The paths A->C and A->C->B are not legal in my graph. The edges are all uni-directional.

Sorry, I made a mistake in the post (and fixed it there). I really believe it will work. Although there may indeed exist better/more efficient ways published...

Tom

[Edited by - dimebolt on August 26, 2005 9:36:13 AM]

Share this post


Link to post
Share on other sites
@dragongame

Thanks for the tip! I'll try the algorithm you described. I think it could work.

@Zefrieg
It don't have to be ultra-evicient. The algorithm is executed at program startup, and not even part of a game.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zoomby
@dimebolt
The paths A->C and A->C->B are not legal in my graph. The edges are all uni-directional.

@Zefrieg

So, I have to do MULTIPLE searches from each node, and one pass over the nodes will never be enough? Then the remaining problem would be to optimize these multiple searches


Yep, for each node you are going to have to run a search beginning at all the other nodes. Optimizations would probably come from certain patterns in the graph that would reduce the need for some of the searches. Computing the minimum spanning tree first might afford some optimizations too. The basic solution seems like it would be O(n^3).

Share this post


Link to post
Share on other sites
What is the graph used for anyway? If the nodes represent spaces in something like a grid, then there are plenty of optimizations for something like that.

Share this post


Link to post
Share on other sites
I have a solution that will work well...

1. Keep a list of both "in" and "out" edges for each node.

Example:
A -> B <- C
Node A: in{null}, out{B}
Node B: in{A,C}, out{null}
Node C: in{null}, out{B}

2. For each node, perform an iterative deepening search that searches the "in" edges of each node. Store the resulting shortest distance tree and/or node distances (whatever you need).

Basically, you would just iterate through the nodes, and there would be one iterative deepening search for each one.

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!