473,320 Members | 1,845 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

how to find the path of shortest distance between two vertices in a graph using bfs

It is also given that in case of a tie, a smaller indexed vertex should be preferable to a larger indexed vertex.


First in my approach i traversed graph using bfs finding distances of all vertices from start node ,i got the path length from start to end node,then i traversed from end node to start node by viewing if the length of node is one less than previous,but i am missing some point in between when i submit my code it is not correct for all test cases,please can someone find what is my mistake.


Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int count=0;
  5.  
  6. struct node{
  7.  
  8.     int value;
  9.     struct node *next;
  10.     struct node *prev;
  11. };
  12.  
  13. struct node *root=NULL,*tra=NULL;
  14.  
  15. void bfs(int n,int a[][n],int start,int end,int value[]){
  16.  
  17.     for(int i=0;i<n ;i++){
  18.  
  19.         if(i==start)
  20.         continue;
  21.  
  22.         if(a[start][i] == 1 ){
  23.  
  24.  
  25.             if(value[i] == 0 || value[i] > value[start] + 1 ){
  26.  
  27.                 value[i] = value[start] + 1;
  28.  
  29.                 struct node *p;
  30.  
  31.                 p = (struct node *)malloc(sizeof(struct node));
  32.                 p->value = i;
  33.                 p->next = root;
  34.                 p->prev = NULL;
  35.                 root->prev = p;
  36.  
  37.                 root = p;
  38.             }
  39.         }
  40.     }
  41.  
  42.     return;
  43. }
  44.  
  45. int main()
  46. {
  47.     int t;
  48.     scanf("%d",&t);
  49.  
  50.     for(int i=0;i<t;i++){
  51.  
  52.         int n;
  53.         scanf("%d",&n);
  54.  
  55.         int a[n][n],start,end,value[n];
  56.         struct node *temp;
  57.  
  58.         for(int j=0;j<n;j++){
  59.             for(int k=0;k<n;k++){
  60.                 scanf("%d",&a[j][k]);
  61.             }
  62.         }
  63.  
  64.  
  65.         memset(value,0,n*4);
  66.         scanf("%d %d",&start,&end);
  67.  
  68.         value[start]=1;
  69.  
  70.         temp = (struct node *)malloc(sizeof(struct node));
  71.         temp->value = start;
  72.         temp->next = NULL;
  73.         temp->prev = NULL;
  74.  
  75.         root = temp;
  76.         tra = temp;
  77.  
  78.  
  79.         while(tra != NULL){
  80.  
  81.             bfs(n,a,tra->value,end,value);
  82.             tra = tra->prev;
  83.         }
  84.  
  85.         printf("%d\n",value[end]-1);
  86.  
  87.         int x = end;
  88.  
  89.         int p[n],pi=0;
  90.         p[pi++] = x;
  91.  
  92.         while(1){
  93.  
  94.             for(int j=0;j<n;j++){
  95.                 if((value[j] == value[x]-1) &&(a[j][x] == 1)){
  96.                     //    printf("%d ",j);
  97.                     p[pi++] = j;
  98.  
  99.                     x=j;
  100.                     break;
  101.  
  102.                 }
  103.             }
  104.             if(x == start){
  105.                 break;
  106.             }
  107.  
  108.         }
  109.  
  110.         for(int j=pi-1;j>=0;j--){
  111.             printf("%d ",p[j]);
  112.  
  113.         }
  114.     }
  115.     return 0;
  116. }
  117.  
Aug 17 '16 #1
0 1193

Sign in to post your reply or Sign up for a free account.

Similar topics

14
by: Job Lot | last post by:
How can I find path of windows folder using vb.net? It could be winnt or windows depending upon the os. System.Environment.SpecialFolder enumeration does not have a constant for windows folder.
11
by: srinivas | last post by:
Hi all, I have one requirement.Is there any way to create a line graph using javascript.If it is please send me the sample code.But the thing is it should work in all browsers. Thanks,...
0
by: ANUPAM | last post by:
Hi All, I have to show Tooltip for Bar/Pie graph using MS charts control in C# which is not available while it is in Visual Basic Version. Please help me. Thansks All, Anupam
0
by: Syazwin | last post by:
Hye everyone! :) i am really a new learner in vb.net. not so expert about what i am searching now.. actually i am looking for the way/source code how to make a line graph in vb.net. the system...
0
by: suedasszyy | last post by:
Haiiii.... i'm new for VB.net. can someone help me to solve those question? is it possible to draw a graph such as Sin graph using console application? if not, how can i draw a graph...
1
by: sainiamit25 | last post by:
Hi, I need to make a graph using javascript based on the values in the oracle table. Can somebody throw some on it? Thanks in advance for your help, Amit
2
by: cmrhema | last post by:
Hi, My client will input two values say A and B. Here A and B represent cities. The source is A and the Destination is B Now i have to find the shortest route for these two cities One is using...
6
by: gubbachchi | last post by:
Hi all, I have got a problem with plotting bar graph using GD. I am learning GD now. I have written the code for basic bar graph with one bar. What I need is, scale on Y-axis i.e. divisions on...
0
by: acheng | last post by:
I want to plot a 3D graph using MathGL. There are three variables (X,Y,Z), and kinds of combination correspond different C values. Also C vector sets the color scheme. I write some codes as below....
0
by: 123pavi | last post by:
Any pointers to algorithms to find "Fundamental Cutsets of a graph or a tree"
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.