CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
user3791843
user3791843

Reputation: 1

How to find nodes at distance less than n from the given node?

In theory, I can use Dijkstra's algorithm to find the distances of all nodes, but if I have a big graph, I will waste a lot of time for calculating distances to remote nodes. Is there some more effecient algorithm?

Upvotes: 0

Views: 270

Answers (2)

user4668606
user4668606

Reputation:

You can use a modified breadth-first-search for this (even for weighted graphs).

listNodes(node start , int maxRange)
    list queue
    set visited
    add(queue , start)
    add(visited , start)

    while ! isEmpty(queue)
        pair p = remove(queue , 0)

        int distTmp = p.dist
        node n = p.node

        //only neighbours that haven't yet been visited
        for node next in disjoint(listNeighbours(n) , visited)
            add(visited , next)//mark as visited
            //store the node in the queue with the distance to start as attribute
            add(queue , pair(next , distTmp + distance(n , next)))

    return visited

If the graph isn't weighted, distance(node , node) will always return 1 for neighbournodes.

Upvotes: 1

j_random_hacker
j_random_hacker

Reputation: 51226

If the edges aren't weighted (or equivalently, if they all have the same weight), you can just run a breadth-first search until the required depth. If they are weighted, Dijkstra's algorithm is your best choice: it also explores nodes in order of increasing distance from the start vertex, so just stop it once the next vertex found is further away than your maximum allowed distance.

Upvotes: 2

Related Questions