Write a program to find a shortest path between any two vertices (from \'a\' to

Question

Write a program to find a shortest path between any two vertices (from 'a' to 'l') in the following graph. You may use the DFS code in the class to start with and represent the graph using either adjacency matrix or adjacency list. The program should take two vertex's names (from 'a' to 'l') and print out the shortest path between them. For example, if the inputs are "a" and "g", then the shortest path should print as "a - b - c - g"; the inputs are "b" and "k", then the shortest path should be "b - f - k". You need to implement the Breadth-first search (BFS) to create a BFS tree starting from one vertex and then you can find the shortest path between the root and any other vertex.

Explanation / Answer

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

vector<int> v[15];

void make_graph();

vector<char> bfs(char a, char b)
{
   int s = (int)(a - 'a'); // changing source node from character to intger
   int d = (int)(b - 'a'); // changing destination node from character to intger;

   int vis[15];
   int par[15];

   memset(vis, 0, sizeof(vis));
   memset(par, -1, sizeof(par));

   queue<int> q;
   q.push(s);
   vis[s] = 1;
   par[s] = -1;

   while(!q.empty()) {
       int cur = q.front();
       q.pop();

       if(cur == d)
           break;

       for(int i = 0; i < v[cur].size(); i++) {
           int nxt = v[cur][i];

           if(!vis[nxt]) {
               par[nxt] = cur; //using parent to store earlier node
               vis[nxt] = 1;
               q.push(nxt);
           }
       }
   }

   int temp = d;
   vector<char> ret; //constructing return value from parent array
   while(temp != -1) {
       ret.pb((char)(temp + 'a'));
       temp = par[temp];
   }
   return ret;
}

void Print(vector<char> x)
{
   int i;
   for(i = x.size()-1; i > 0; i--) {
       cout << x[i] << " - ";
   }
   cout << x[0] << endl;
}

int main()
{

   make_graph();
   char a, b;

   while(true) {
       cin >> a >> b;
       Print(bfs(a, b));
   }
   return 0;
}

void make_graph() {

   /**
   The nodes are numbered from 0 to 11, 0 representing 'a' and 11 representing 'l'
   We have used Adjacency List for graph creation
   */

   v[0].pb(1);
   v[0].pb(4);

   v[1].pb(0);
   v[1].pb(2);
   v[1].pb(5);

   v[2].pb(1);
   v[2].pb(6);

   v[3].pb(7);  

   v[4].pb(0);
   v[4].pb(5);
   v[4].pb(8);

   v[5].pb(1);
   v[5].pb(4);
   v[5].pb(9);
   v[5].pb(10);

   v[6].pb(2);
   v[6].pb(10);

   v[7].pb(3);
   v[7].pb(11);

   v[8].pb(4);
   v[8].pb(9);

   v[9].pb(5);
   v[9].pb(8);

   v[10].pb(5);
   v[10].pb(6);
   v[10].pb(11);

   v[11].pb(7);
   v[11].pb(10);
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.