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

## Recommended Posts

Quote:
Original post by dimebolt
Quote:
 Original post by Zoomby@dimeboltNo, 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 on other sites
@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 on other sites
Quote:
 Original post by ZefriegDude, 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 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 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 on other sites
Quote:
 Original post by Zoomby@dimeboltThe 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 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 on other sites
Quote:
 Original post by Zoomby@dimeboltThe paths A->C and A->C->B are not legal in my graph. The edges are all uni-directional.@ZefriegSo, 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 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 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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 15
• 25
• 12
• 11
• ### Forum Statistics

• Total Topics
634794
• Total Posts
3019314
×