Scribd
Upload
13 views

DM Assignment 1 Answer

Uploaded by

Ankit Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views

DM Assignment 1 Answer

Uploaded by

Ankit Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

SRM Institute of Science and Technology

Ramapuram Campus
Department of Mathematics
Assignment
21MAB302T–Discrete Mathematics
1. Write a C Program to Find the Transitive Closure of a Graph using Warshall’s Algorithm.
Ans

1. #include<stdio.h>
2. #include<conio.h>
3. #include<math.h>
4. int max(int, int);
5. void warshal(int p[10][10], int n) {
6. int i, j, k;
7. for (k = 1; k <= n; k++)
8. for (i = 1; i <= n; i++)
9. for (j = 1; j <= n; j++)
10. p[i][j] = max(p[i][j], p[i][k] && p[k][j]);
11. }
12. int max(int a, int b) {
13. ;
14. if (a > b)
15. return (a);
16. else
17. return (b);
18. }
19. void main() {
20. int p[10][10] = { 0 }, n, e, u, v, i, j;
21. printf("\n Enter the number of vertices:");
22. scanf("%d", &n);
23. printf("\n Enter the number of edges:");
24. scanf("%d", &e);
25. for (i = 1; i <= e; i++) {
26. //printf("\n Enter the end vertices of edge %d:", i);
27. scanf("%d%d", &u, &v);
28. p[u][v] = 1;
29. }
30. printf("\n Matrix of input data: \n");
31. for (i = 1; i <= n; i++) {
32. for (j = 1; j <= n; j++)
33. printf("%d\t", p[i][j]);
34. printf("\n");
35. }
36. warshal(p, n);
37. printf("\n Transitive closure: \n");
38. for (i = 1; i <= n; i++) {
39. for (j = 1; j <= n; j++)
40. printf("%d\t", p[i][j]);
41. printf("\n");
42. }
43. getch();
44. }
45. $ gcc WarshallTransitiveClosure.c
46. $ ./a.out
47.
48. Enter the number of vertices: 5
49. Enter the number of edges: 11
50. Enter the end vertices of edge 1: 1 1
51. Enter the end vertices of edge 2: 1 4
52. Enter the end vertices of edge 3: 3 2
53. Enter the end vertices of edge 4: 3 3
54. Enter the end vertices of edge 5: 3 4
55. Enter the end vertices of edge 6: 4 2
56. Enter the end vertices of edge 7: 4 4
57. Enter the end vertices of edge 8: 5 2
58. Enter the end vertices of edge 9: 5 3
59. Enter the end vertices of edge 10: 5 4
60. Enter the end vertices of edge 11: 5 5
61.
62. Matrix of input data:
63. 1 0 0 1 0
64. 0 0 0 0 0
65. 0 1 1 1 0
66. 0 1 0 1 0
67. 0 1 1 1 1
68.
69. Transitive closure:
70. 1 1 0 1 0
71. 0 0 0 0 0
72. 0 1 1 1 0
73. 0 1 0 1 0
74. 0 1 1 1 1

2.Write a C Program to Implement Floyd-Warshall Algorithm


1. // Program for Floyd Warshall Algorithm
2. #include<stdio.h>
3.
4. #define V 4 // Number of vertices in the graph
5.
6. /* Define Infinite as a large enough value. This value will be used
7. for vertices not connected to each other */
8. #define INF 99999
9.
10. // A function to print the solution matrix
11. void printSolution(int dist[][V]);
12.
13. // Solves the all-pairs shortest path problem using Floyd
Warshall algorithm
14. void floydWarshell(int graph[][V])
15. {
16. int dist[V][V], i, j, k;
17.
18. /* Initialize the solution matrix same as input graph
matrix. Or
19. we can say the initial values of shortest distances are
based
20. on shortest paths considering no intermediate vertex. */
21. for (i = 0; i < V; i++)
22. for (j = 0; j < V; j++)
23. dist[i][j] = graph[i][j];
24.
25. for (k = 0; k < V; k++)
26. {
27. // Pick all vertices as source one by one
28. for (i = 0; i < V; i++)
29. {
30. // Pick all vertices as destination for the
31. // above picked source
32. for (j = 0; j < V; j++)
33. {
34. // If vertex k is on the shortest path from
35. // i to j, then update the value of dist[i][j]
36. if (dist[i][k] + dist[k][j] < dist[i][j])
37. dist[i][j] = dist[i][k] + dist[k][j];
38. }
39. }
40. }
41.
42. // Print the shortest distance matrix
43. printSolution(dist);
44. }
45.
46. /* A utility function to print solution */
47. void printSolution(int dist[][V])
48. {
49. printf("Following matrix shows the shortest distances"
50. " between every pair of vertices \n");
51. int i, j;
52. for (i = 0; i < V; i++)
53. {
54. for (j = 0; j < V; j++)
55. {
56. if (dist[i][j] == INF)
57. printf("%7s", "INF");
58. else
59. printf("%7d", dist[i][j]);
60. }
61. printf("\n");
62. }
63. }
64.
65. // driver program to test above function
66. int main()
67. {
68. /* Let us create the following weighted graph
69. 10
70. (0)------->(3)
71. | /|\
72. 5 | |
73. | | 1
74. \|/ |
75. (1)------->(2)
76. 3 */
77. int graph[V][V] = { { 0, 5, INF, 10 },
78. { INF, 0, 3, INF },
79. { INF, INF, 0, 1 },
80. { INF, INF, INF, 0 }
81. };
82.
83. // Print the solution
84. floydWarshell(graph);
85. return 0;
86. }
Program Explanation
1. Define number of vertices in the graph.
2. Define Infinite as a large enough value. This value will be used for the vertices that are not connected to
each other.
3. dist[][] will be the output matrix that will finally have the shortest distance between every pair of vertices.
4. Initialize the solution matrix same as input graph matrix.
5. Add all vertices one by one to the set of intermediate vertices.
6. Before beginning an iteration, we have shortest distances between all pairs of vertices such that the shortest
distances consider just the vertices in set {0, 1, 2,… k-1} as intermediate vertices.
7. After the end of a iteration, vertex no. k is added to the set of intermediate vertices and the set becomes {0,
1, 2, .. k}
8. Pick all vertices as source one by one and if vertex k is on the shortest path from i to j, then update the value
of dist[i][j].
9. Print the shortest distance matrix.

Out put
Following matrix shows the shortest distances between every pair of vertices
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0

You might also like