CODEWITHSUNDEEP
c++graphtraversalbreadth-first-search
maregor
maregor

Reputation: 797

Getting shortest path between two nodes with BFS algorithm

I'm trying to do Breadth-First Search traversal through a graph of nodes, after which I will try to find the shortest distance between a Node and another. This is what wikipedia's BFS algorithm looks like:

  procedure BFS(G,v) is
      let Q be a queue
      Q.push(v)
      label v as discovered
      while Q is not empty
         v ← Q.pop()
         for all edges from v to w in G.adjacentEdges(v) do
             if w is not labeled as discovered   
                 Q.push(w)
                label w as discovered

I have my own Node class with the distance of the Nodes set to max. My version based on the style of the first code:

class Node { // my version
  string name;
  vector<Node*> adj;
  int dist; // initially set to int max
  int prev;
  int index;
}

procedure BFS(G, Node* v)
    let Q be a queue
    v->distance = 0
    Q.push(v)
    label v as discovered
    while Q is not empty
      Node* n = q.front();
      v = Q.pop()
      for each node w adj vector of n
         Node* neighbor = G[w]
         if neighbor->distance == max
           neighbor->distance = n->distance + 1
           neighbor->prev = n->index
           q.push(neighbor)

I'm trying to make this code also find the shortest path between a node and another node. e.g.

procedure BFS(G, Node* from, Node* to)

How can I modify the BFS code to do this? If it's not possible inside this loop, what other way is there to do it?

Please inform me if there is any confusion with my code or what I'm asking. Thank you!

Upvotes: 0

Views: 8501

Answers (1)

Heinrich du Toit
Heinrich du Toit

Reputation: 458

Usually the BFS algorithm is simply in order to walk all the nodes in the graph in a breath first manner. As apposed to a DFS (depth first) algorithm which is usually implemented using recursion.

For the purpose of finding the shortest distance you need to modify the algorithm:

if neighbor->distance == max

needs to be:

if neighbor->distance > n->distance+1

Although this will result in exactly the same algorithm. But if the edges of the graph have distances other than 1 then this is required.

Using your algorithm trying to find shortest distance from nodeA to nodeB

  1. run BFS(G,nodeA)
  2. The answer is in nodeB->distance
  3. You can also find the shortest path by walking back via node->prev then over the graph until you reach nodeA

If all the edge's have distance 1 you can stop the algorithm the moment you find nodeB the first time. However if your edges have variable distance you will need to run the BFS algorithm to completion.

The best way to find the shortest path between 2 nodes in a graph is usually done by using Dijkstra's Algorithm

It has some similarities to a Breath First Search but is faster because of the usage of the priority queue.

Upvotes: 1

Related Questions