I'm searching a graph algorithm

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.

You can probably use a variation of Dijkstra's Algorithm, where the edge weights are all one.

@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

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

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 :-)

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.

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.

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 :)

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

Are the edges weighted?

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?

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

@Zefrieg

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

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

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

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

@dimebolt
No, you are not allowed to go back in the graph I use.

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]

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.