Description

Assignment no. 6
Objective To implement BFS and to use it to solve single-source shortest path problem on undirected graphs
Total marks 10
Penalty for violating naming convention(s) 5%
Input
Your program should accept an input file as a command-line argument. A typical execution of your program will be ./a.out sample.graph
The input file represents an undirected graph. The first line of the file contains two numbers: (i) the number of vertices n; (ii) the number of edges m. The vertices are numbered from 0 to n-1. Every other line is of the form: x y, which represents an undirected edge between vertex x and y. No edge is repeated in the input file. The vertex 0 is the source (starting) vertex from which you need to find the shortest distances to other vertices.
Task
Implement BFS and use it to find the shortest distance of every vertex from the source vertex (0). The output file should be named as ‘sd.txt’. Every line in the output file should have exactly one integer which represents the distance between the source vertex and the vertex with label k-1, where k is the line number. For example, the first line should have the distance between the source vertex 0 and the vertex 0 – of course, this value is always 0. The output file must have exactly n lines. The graph that will be used for evaluation will have at least 1000 vertices and at most 2000 vertices.
Note#1: if there is no path exists from the source vertex 0 to any other given vertex (means if no shortest path exists from the source vertex), then the output file should contain “-1” at that vertex
Note#2: if there is no vertex is presented in the given input file, in that case also the output file should contain value “-1” at that vertex
Submission
● The program you submit should output ‘sd.txt’ when run.
● The main file of your program should be named as <roll no>.<extension>, where roll no. specifies your roll no. and the extension depends on the language you choose (Usage of C is mandatory for this assignment). Ex: 200010001.c.
● Follow some coding style uniformly. Provide proper comments in your code.
● Submit only through moodle. Submit well in advance. Any hiccups in the moodle/internet at the last minute is never acceptable as an excuse for late submission. Submissions through email or any other means will be ignored.
Evaluation
● We will do the second evaluation later. This is for those who want to improve their marks obtained in the first evaluation or who do not submit for the first evaluation.
There will be a penalty of 20% for those who are submitting for the second evaluation.
The details of the second evaluation will be shared later.