Hi, what is the best algorithm to find the value "how many nodes (steps) away is a specific node (the smallest possible number of steps)" for each edge of a graph? This specific node is known before the algorithm. I would use a breath-first to find the nodes. And then for each found node use another depth-first to find the shortest way to the specified node. But maybe there's a better way. Bye Chris

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.

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.

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.