CS2094D Assignment-5 Solution

Policies for Submission and Evaluation

Naming Conventions for Submission
Submit a single ZIP (.zip) file (do not submit in any other archived formats like .rar or .tar.gz).
The name of this file must be ASSG<NUMBER>_<ROLLNO>_<FIRSTNAME>.zip. (For example: ASSG4_BxxyyyyCS_LAXMAN.zip). DO NOT add any other files (like temporary files, inputfiles, etc.) except your source code, into the zip archive. The source codes must be named as ASSG<NUMBER>_<ROLLNO>_<FIRSTNAME>_<PROGRAM-NO>.<extension>.
(For example: ASSG4_BxxyyyyCS_LAXMAN_1.c). If there are multiple parts for a particular question, then name the source files for each part separately as in
ASSG4_BxxyyyyCS_LAXMAN_1b.c.
If you do not conform to the above naming conventions, your submission might not be recognized by some automated tools, and hence will lead to a score of 0 for the submission. So, make sure that you follow the naming conventions.

Standard of Conduct
http://minerva.nitc.ac.in/cse/sites/default/files/attachments/news/Academic-Integrity_new.pdf



1. Write programs that compute the minimum spanning tree of a connected undirected graph using the following algorithms:
a. Kruskal’s algorithm
b. Prim’s algorithm

Input format:

●The first line of the input contains a positive integer n , the number of vertices in the graph, in the range 1 to 1000.
● The subsequent n lines contain the labels of the nodes adjacent to the respective nodes, sorted in ascending order from left to right.
● The subsequent n lines contain the weights of the edges corresponding to the adjacency list. The edge weights are real numbers in the range [-10000, 10000]. Further, no two edges have the same weight.

Output format:

Single line containing the sum of the edge weights of the minimum spanning tree.

Note -
In a graph with n vertices, the vertices are labeled from 0 to n -1. Use adjacency lists to store the graphs, with the vertices sorted in ascending order. The adjacency list of each node is a singly linked list that contains its adjacent nodes sorted in ascending order from left to right. The nodes in this list contain two fields, namely, the label of the adjacent node and the weight of the edge, if provided. Unless specified otherwise, the adjacency lists must be processed iteratively from left to right.



Sample Input and Output ( Same for 1a and 1b )

Input

7
1 5
0 2 6
1 3
2 4 6
3 5 6
0 4
1 3 4
28 10
28 16 14 16 12
12 22 18
22 25 24 10 25
14 18 24

Output

99


2. Given a directed graph G = (V , E ), edge weights w ≥0, source s ∈ V , find the weight of shortest path from s to all other vertices.

Input Format

● First line is the number of nodes (V) in a graph. Vertices are labelled from 0 to V-1.
● Second line is the number of edges (E) in a graph.
● Next E lines each line consist of three space separated integers x y z, where x and y denote the two nodes between which the directed edge exist and z is the weight of the edge.
● Next line consists of one integer s, where s denotes the source node.

Output Format

● Print the destination node and weight associated with it. If there is no path print “INF”

Sample Input and Output

Input

4
4
0 1 1
0 3 4
2 1 2
3 2 5
0

Output

0 0
1 1
2 9
3 4

3. Write a C program to check if there is a negative cycle in a directed graph. A negative cycle is one in which the overall sum of the weights in the cycle is negative.

Input Format

● First line contains two integers n , m denoting number of vertices and number of edges present in a directed graph
● Next m lines contains 3 integers x , y , w denoting there is an directed edge from x to y having a weight w

Output Format

● Print 1 if there is negative cycle otherwise print -1
Note: - The vertices are labeled from 0 to n-1

Sample Input and Output

Input

5 8
0 1 -1
0 2 4
1 2 3
1 3 2
1 4 2
3 2 5
3 1 1
4 3 -3

Output

-1