# I'm searching a graph algorithm

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

## Recommended Posts

Are the edges weighted?

##### Share on other sites
Quote:
 Original post by Zoomby@C0D1F1EDThis 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 on other sites
Quote:
 Original post by Zoomby@dragongameSo 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 on other sites
@Zefrieg

No, the graph is directed as dragongame said. It is not weighted.

##### 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 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 on other sites
Quote:
 Original post by Zoomby@dimeboltAs 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 on other sites
@dimebolt
No, you are not allowed to go back in the graph I use.

##### Share on other sites
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 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 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.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 9
• 15
• 9
• 11