473,749 Members | 2,384 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

48 New Member
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 1217

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

Similar topics

14
18347
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
14895
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, Srinivas
0
1401
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
5812
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 will display a graph after user enter the coordinates.beside will display the maximum and minimum point/coordinate + the graph can be save as a picture for reference in the future.i have search but not really understand to use the coding with the...
0
2707
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 ,example sin graph in window form but i must give the commands in console application ?
1
2131
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
1323
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 Dijktra's algorithm. But there one has two provide the other values too. eg He starts from A and reaches to B, via A1,A2,A3, B1,B2,B3 we get all the distances from one place to all the above mentioned places and can find out the shortest path.
6
2593
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 y-axis like 500,1000,1500 upto value which I have mentioned in $max variable which in my case is 4000. Here is the code <?php header("Content-type: image/jpeg");
0
2066
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. But it doesn't work. I'm not sure I use wrong functions or not. mglData x("x"),y("y"),z("z"),c("c"); mglGraph *gr=new mglGraphZB; gr->SetSize(1200,800);gr->Title("Eletron Density",0,5); gr->Rotate(65,35); gr->XRange(x); gr->YRange(y);...
0
2868
by: 123pavi | last post by:
Any pointers to algorithms to find "Fundamental Cutsets of a graph or a tree"
0
8832
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9566
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
9388
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9333
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9254
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
8256
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6800
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4879
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3319
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

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.