C-Codes/WeightGraphMatrix.c at master · gunanksood/C-Codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define INFINITE 10000000
int search( char nodes[] , int size , char ch )
{
	int index = -1;
	int i;
	for( i = 0; i < size; i++ )
	{
		if( ch == nodes[i] )
		{
			index = i;
			break;
		}
	}
	return index;
}
int main()
{
	char nodes[MAX],ch,start,end;
	int graph[MAX][MAX] = {};
	int weights[MAX][MAX] = {};
	int size , i , j , k,weight,choice;
	printf("\n Enter Total Number of Vertices : ");
	scanf("%d",&size);
	i = 0;
	while( 1 )
	{
		if( i == size )
		{
			break;
		}
		fflush(stdin);
		printf("\n Enter Node Name : ");
		scanf("%c",&ch);
		if( search( nodes , i , ch ) == -1 )
		{
			nodes[i] = ch;
			i++;
		}
		else
		{
			printf("\n This Node Name is used Try With Different Name \n");
		}
	}
	printf("\n Nodes List : ");
	for( i = 0; i < size; i++ )
	{
		printf(" [ %c ] ",nodes[i]);
	}
	printf("\n");
	while( 1 )
	{
		fflush(stdin);
		printf("\n Enter Start Node : ");
		scanf("%c",&start);
		fflush(stdin);
		printf("\n Enter End Node : ");
		scanf("%c",&end);
		i = search( nodes , size , start );
		j = search( nodes , size , end );
		if( i != -1 && j != -1 )
		{
			printf("\n Enter Weight : ");
			scanf("%d",&weight);
			graph[i][j] = weight;
		}
		else
		{
			printf("\n Invalid Node Name Given \n");
		}
		printf("\n Press 1 For Add More Edges. Enter Your Choice : ");
		scanf("%d",&choice);
		fflush(stdin);
		if( choice != 1 )
		{
			break;
		}
	}
	printf("\n Weighted Graph Adjacency Matrix \n ");
	for( i = 0; i < size; i++ )
	{
		printf("\t%c",nodes[i]);
	}
	for( i = 0; i < size; i++ )
	{
		printf("\n %c",nodes[i]);
		for( j = 0; j < size; j++ )
		{
			printf("\t%d",graph[i][j]);
		}
		printf("\n");
	}
	// Shortest Path
	for( i = 0; i < size; i++ )
	{
		for( j = 0; j < size; j++ )
		{
			if( graph[i][j] == 0 )
			{
				weights[i][j] = INFINITE;
			}
			else
			{
				weights[i][j] = graph[i][j];
			}
		}
	}
	for( k = 0; k < size; k++ )
	{
		for( i = 0; i < size; i++ )
		{
			for( j = 0; j < size; j++ )
			{
				if( weights[i][j] > ( weights[i][k] + weights[k][j] ))
				{
					if( weights[i][k] == INFINITE || weights[k][j] == INFINITE )
					{
						weights[i][j] = INFINITE;
					}
					else
					{
						weights[i][j] = weights[i][k] + weights[k][j];
					}
				}
			}
		}
	}
	for( i = 0; i < size; i++ )
	{
		for( j = 0; j < size; j++ )
		{
			if( weights[i][j] == INFINITE )
			{
				weights[i][j] = 0;
			}
		}
	}
	printf("\n Shortest Path Graph Adjacency Matrix \n ");
	for( i = 0; i < size; i++ )
	{
		printf("\t%c",nodes[i]);
	}
	for( i = 0; i < size; i++ )
	{
		printf("\n %c",nodes[i]);
		for( j = 0; j < size; j++ )
		{
			printf("\t%d",weights[i][j]);
		}
		printf("\n");
	}
	return 0;
}