# Shortest path using BFS in graph

Page 1 of 1

## 7 Replies - 5600 Views - Last Post: 11 September 2012 - 10:43 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=291609&amp;s=a228e5f16d37d6722bd89b213ea1444c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 vikrantiitr_1

Reputation: 0
• Posts: 6
• Joined: 11-July 12

# Shortest path using BFS in graph

Posted 11 September 2012 - 09:07 AM

I was trying to find shortest path using modern adjacency list graph data structure and BFS algorithm. I am not getting any output after passing required inputs and it is still running. This usually happens when the loop don't terminate but I am not able to figure it out here....
```#include<iostream>
using namespace std;

class vertex;
class Graph;

void BFS(Graph,int);

struct Edge{
int E_num;
vertex*first;
vertex*second;
Edge*enext;
};

struct node{
Edge*data;          // node of edgelist inside a vertex
node*next;          // Here we can also store vertex numbers to get adjacent vertices quickly.
};

class vertex{
public:
int V_num;
node*E_in_front;
node*E_in_rear;
node*E_out_front;
node*E_out_rear;
vertex*vnext;
int color;
int label;
int parent;

vertex(){
E_in_front = E_in_rear = NULL;
E_out_front = E_out_rear = NULL;
color = 0; // initially white.
label = -1;
parent = -1;
}

void insert_node_vin(Edge*x)
{
node*temp = new node;
temp->data = x;
temp->next = NULL;
if(E_in_front == NULL)
{
E_in_front = E_in_rear = temp;
return;
}
E_in_rear->next = temp;
E_in_rear = temp;
}

void insert_node_vout(Edge*x)
{
node*temp = new node;
temp->data = x;
temp->next = NULL;
if(E_out_front == NULL)
{
E_out_front = E_out_rear = temp;
return;
}
E_out_rear->next = temp;
E_out_rear = temp;
}

};

class Graph{

public:

Edge*E_front;
Edge*E_rear;
vertex*V_front;
vertex*V_rear;

Graph(){
E_front = E_rear = NULL;
V_front = V_rear = NULL;
}

void insert_edge(int v1, int v2, int num) // num = edge number input by user.
{
if(ispresent(v1))
{
if(ispresent(v2))
{ // just create an edge with starting vertex v1 and ending v2.
Edge*temp = new Edge;
temp->E_num = num;
vertex*temp1 = V_front;
vertex*temp2 = V_front;
while(temp1 != NULL)
{
if(temp1->V_num == v1)
break;
temp1 = temp1->vnext;
}
while(temp2 != NULL)
{
if(temp2->V_num == v2)
break;
temp2 = temp2->vnext;
}
E_rear->enext = temp;
temp->enext = NULL;
E_rear =  temp;
temp1->insert_node_vout(temp);
temp2->insert_node_vin(temp);

temp->first = temp1;
temp->second = temp2;
}
else
{
Edge*temp = new Edge;
temp->E_num = num;
vertex*temp1 = V_front;
while(temp1 != NULL)
{
if(temp1->V_num == v1)
break;
temp1 = temp1->vnext;
}
E_rear->enext = temp;
temp->enext = NULL;
E_rear =  temp;
vertex*temp2 = new vertex;
temp2->V_num = v2;
V_rear->vnext = temp2;
temp2->vnext = NULL;
V_rear = temp2;

temp1->insert_node_vout(temp);
temp2->insert_node_vin(temp);

temp->first = temp1;
temp->second = temp2;
}
}
else // if v1 is not present.
{
if(ispresent(v2))
{
Edge*temp = new Edge;
temp->E_num = num;
vertex*temp2 = V_front;
while(temp2 != NULL)
{
if(temp2->V_num == v2)
break;
temp2 = temp2->vnext;
}
E_rear->enext = temp;
temp->enext = NULL;
E_rear =  temp;
vertex*temp1 = new vertex;
temp1->V_num = v1;
V_rear->vnext = temp1;
temp1->vnext = NULL;
V_rear = temp1;

temp1->insert_node_vout(temp);
temp2->insert_node_vin(temp);

temp->first = temp1;
temp->second = temp2;
}
else  // both v1 and v2 are not present. It means either there are no elements in graph or only v1 & v2 are not present.
{
Edge*temp = new Edge;
temp->E_num = num;
if(E_front  == NULL)
{
E_front = E_rear = temp;
temp->enext = NULL;
}
else
{
E_rear->enext = temp;
temp->enext = NULL;
E_rear =  temp;
}
vertex*temp1 = new vertex;
temp1->V_num = v1;
vertex*temp2 = new vertex;
temp2->V_num = v2;
if(V_front  == NULL)
{
V_front = V_rear = temp1;
temp1->vnext = temp2;
temp2->vnext = NULL;
V_rear = temp2;
}
else
{
V_rear->vnext = temp1;
temp1->vnext = temp2;
temp2->vnext = NULL;
V_rear = temp2;
}

temp1->insert_node_vout(temp);
temp2->insert_node_vin(temp);

temp->first = temp1;
temp->second = temp2;
}
}
}                                    // End void insert_edge(v1,v2,num).

bool ispresent(int v)
{
if(V_front == NULL)
return false;

vertex*temp = V_front;
while(temp != NULL)
{
if(temp->V_num == v)
return true;
temp = temp->vnext;
}
return false;
}

int label_vertex(int v)
{
vertex*temp = V_front;
while(temp != NULL)
{
if(temp->V_num == v)
return temp->label;
temp = temp->vnext;
}

return 0;
}
};                                               // END OF CLASS GRAPH.

int main()
{
Graph G;
int v1=-1,v2,edgenum;
cin>>v1>>v2>>edgenum;
while(v1 != -1)
{
G.insert_edge(v1,v2,edgenum);
cin>>v1;
if(v1==-1)
break;
cin>>v2>>edgenum;
}
/* Now we have to define three arrays:- color, label, parent. For that either of steps can be taken:
i) use a data member size in class graph and increment with each vertex addition
ii)use three more data member inside vertex class ,namely color, label, parent.
We will be using ii) case as it is more complex to implement.
*/
cout<<"Enter the vertices between whom shortest distance is to be find out: ";
cin>>v1>>v2;
/* Here we will label all the vertex to practice.Otherwise there is no need of this because start BFS from v1 and when we get v2 print its
label & also no need of taking "label" as data member because we have to just ++ a variable initialise to 0 whenever we pop-out of
queue and no need of labelling all intermediate vertices.But we do it here.
*/

BFS(G,v1); // as discussed above this would change to BFS(G,v1,v2) and just return shortest distance directly.

int shortest_path = G.label_vertex(v2) - G.label_vertex(v2);

cout<<"Shortest path between "<<v1<<" and "<<v2<<" is : "<<shortest_path<<endl;
// WE CAN ALSO STATE THE PATH TAKEN.
system("pause");
return 0;
}

struct queuenode{
vertex*vpointer;
queuenode*next;
};

class queue{
public:
queuenode*front;
queuenode*rear;
int length;

queue(){ front = NULL;
rear = NULL;
length = 0;
}

void enqueue(vertex*x)
{
queuenode*newnode = new queuenode;
newnode->vpointer = x;
newnode->next = NULL;
if(length==0)
{
front = rear = newnode;
length++;
return;
}

rear->next = newnode;
length++;
rear = newnode;
}

void dequeue(){
if(front == NULL)
return;

queuenode*temp = front;
front = front->next;
delete temp;
length--;
}
};

void BFS(Graph G, int v)
{
vertex*temp = G.V_front;         // Here we have taken "." instead of "->" in G.V_front.This is because "->" is taken only when object
while(temp->V_num != v)          // is of pointer type, like Graph*G.Thanks!!
temp = temp->vnext;

queue q;
q.enqueue(temp);
temp->color = 1;  // gray- visited once and push in queue.
temp->label = 0;  // level of that element.
while(q.length != 0)  // queue is not empty.
{
queuenode*temp1 = q.front;
node*temp2 = temp->E_out_front;
while(temp2 != NULL)
{
q.enqueue(temp2->data->second);
temp2->data->second->label = temp1->vpointer->label + 1;
temp2->data->second->color = 1;
temp2->data->second->parent = temp1->vpointer->V_num;
temp2 = temp2->next;
}
q.dequeue();
temp1->vpointer->color = 2;
}

}

```

here inputs can be given like this:-
1 2 1
and give v1=-1 to stop inputs.

has anyone caught the bugs??

Is This A Good Question/Topic? 0

## Replies To: Shortest path using BFS in graph

### #2 jimblumberg

Reputation: 4565
• Posts: 14,417
• Joined: 25-December 09

## Re: Shortest path using BFS in graph

Posted 11 September 2012 - 09:13 AM

You may want to add some prompts to your inputs. After entering enough inputs this program seems to seg fault. You may want to run the program through your debugger and try to find where the crash happens and the cause.

Jim

### #3 vikrantiitr_1

Reputation: 0
• Posts: 6
• Joined: 11-July 12

## Re: Shortest path using BFS in graph

Posted 11 September 2012 - 09:20 AM

jimblumberg, on 11 September 2012 - 09:13 AM, said:

You may want to add some prompts to your inputs. After entering enough inputs this program seems to seg fault. You may want to run the program through your debugger and try to find where the crash happens and the cause.

Jim

can you figure out any one??

### #4 jimblumberg

Reputation: 4565
• Posts: 14,417
• Joined: 25-December 09

## Re: Shortest path using BFS in graph

Posted 11 September 2012 - 09:30 AM

First add prompts for your inputs so you know what you are inputting where. Then run the program through your debugger. Your debugger will show you where it detects the problem.

Jim

### #5 vikrantiitr_1

Reputation: 0
• Posts: 6
• Joined: 11-July 12

## Re: Shortest path using BFS in graph

Posted 11 September 2012 - 10:31 AM

jimblumberg, on 11 September 2012 - 09:30 AM, said:

First add prompts for your inputs so you know what you are inputting where. Then run the program through your debugger. Your debugger will show you where it detects the problem.

Jim

Finally....finally it works...this technique of detecting faults using prompts is awesome and give bit-to-bit explanation of what's happening around. Thanks Jim for telling this technique!! It detected lots of bugs.
Final code:- http://ideone.com/TKUD2.
It's working on my test cases now, if anyone finds test cases where it fails, please post!!thanks..

sorry.. remove "." in above url... its

http://ideone.com/TKUD2

### #6 jimblumberg

Reputation: 4565
• Posts: 14,417
• Joined: 25-December 09

## Re: Shortest path using BFS in graph

Posted 11 September 2012 - 10:35 AM

Why not just post your code in your post, inside code tags?

Spoiler

Jim

This post has been edited by jimblumberg: 11 September 2012 - 10:35 AM

### #7 vikrantiitr_1

Reputation: 0
• Posts: 6
• Joined: 11-July 12

## Re: Shortest path using BFS in graph

Posted 11 September 2012 - 10:37 AM

i am not getting edit option...where is it??

### #8 jimblumberg

Reputation: 4565
• Posts: 14,417
• Joined: 25-December 09

## Re: Shortest path using BFS in graph

Posted 11 September 2012 - 10:43 AM