Scribd
Upload
5 views11 pages

C Programs for Advanced Algorithms

The document contains a series of C programs implementing advanced algorithms for network flow and shortest path calculations. It includes a maximum flow algorithm using Depth First Search (DFS), a maximum flow algorithm using Breadth First Search (BFS), and the Floyd-Warshall algorithm for finding all pairs shortest paths. Each program prompts the user for input and displays the results, with the author's name and registration number included at the end.

Uploaded by

s.Karthi Keyan 640
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views11 pages

C Programs for Advanced Algorithms

The document contains a series of C programs implementing advanced algorithms for network flow and shortest path calculations. It includes a maximum flow algorithm using Depth First Search (DFS), a maximum flow algorithm using Breadth First Search (BFS), and the Floyd-Warshall algorithm for finding all pairs shortest paths. Each program prompts the user for input and displays the results, with the author's name and registration number included at the end.

Uploaded by

s.Karthi Keyan 640
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

ADVANCED ALGORITHMS

LAB
ASSIGNMENT – I

NAME :KARTHIKEYAN S
[Link]: 24MID0093
C PROGRAM :
#include<stdio.h>

#include<string.h>

#include<limits.h>

int n,m;

int cap[100][100];

int vis[100];

int min(int a,int b){

return a<b?a:b;

int dfs(int u,int t,int flow){

if(u==t) return flow;

vis[u]=1;

for(int v=0;v<n;v++){

if(!vis[v] && cap[u][v]>0){

int cur=dfs(v,t,min(flow,cap[u][v]));
if(cur>0){

cap[u][v]-=cur;

cap[v][u]+=cur;

return cur;

return 0;

int main(){

printf("Enter number of nodes and edges: ");

scanf("%d %d",&n,&m);

memset(cap,0,sizeof(cap));

printf("Enter edges (u v capacity):\n");

for(int i=0;i<m;i++){

int u,v,w;

scanf("%d %d %d",&u,&v,&w);

cap[u][v]+=w;

int s,t;

printf("Enter source and sink: ");

scanf("%d %d",&s,&t);

int flow=0;

while(1){
memset(vis,0,sizeof(vis));

int pushed=dfs(s,t,INT_MAX);

if(pushed==0) break;

flow+=pushed;

printf("Maximum Flow = %d\n",flow);

printf("\n DONE BY : \n KARTHIKEAYN S \n 24MID0093 \n");

return 0;

OUTPUT :
C PROGRAM :
#include<stdio.h>

#include<string.h>

#include<limits.h>

int n,m;

int cap[100][100],par[100];

int bfs(int s,int t){

int q[100],front=0,rear=0;

int vis[100];

memset(vis,0,sizeof(vis));

q[rear++]=s;

vis[s]=1;

par[s]=-1;

while(front<rear){

int u=q[front++];

for(int v=0;v<n;v++){

if(!vis[v] && cap[u][v]>0){

q[rear++]=v;
par[v]=u;

vis[v]=1;

if(v==t) return 1;

return 0;

int main(){

printf("Enter number of nodes and edges: ");

scanf("%d %d",&n,&m);

memset(cap,0,sizeof(cap));

printf("Enter edges (u v capacity):\n");

for(int i=0;i<m;i++){

int u,v,w;

scanf("%d %d %d",&u,&v,&w);

cap[u][v]+=w;

int s,t;

printf("Enter source and sink: ");

scanf("%d %d",&s,&t);

int flow=0;

while(bfs(s,t)){

int path=INT_MAX;
for(int v=t;v!=s;v=par[v]){

int u=par[v];

if(cap[u][v]<path) path=cap[u][v];

for(int v=t;v!=s;v=par[v]){

int u=par[v];

cap[u][v]-=path;

cap[v][u]+=path;

flow+=path;

printf("Maximum Flow = %d\n",flow);

printf("\n DONE BY : \n KARTHIKEAYN S \n 24MID0093 \n");

return 0;

OUTPUT :
C PROGRAM :
#include<stdio.h>

#define INF 1000000000

int n,m;

int dist[100][100];

int main(){

printf("Enter number of nodes and edges: ");

scanf("%d %d",&n,&m);

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

if(i==j) dist[i][j]=0;

else dist[i][j]=INF;

printf("Enter edges (u v weight):\n");

for(int i=0;i<m;i++){
int u,v,w;

scanf("%d %d %d",&u,&v,&w);

dist[u][v]=w;

for(int k=0;k<n;k++){

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

if(dist[i][k]+dist[k][j]<dist[i][j]){

dist[i][j]=dist[i][k]+dist[k][j];

printf("All Pairs Shortest Path Matrix:\n");

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

if(dist[i][j]>=INF) printf("INF ");

else printf("%d ",dist[i][j]);

printf("\n");

printf("\n DONE BY : \n KARTHIKEAYN S \n 24MID0093 \n");

return 0;

}
OUTPUT :

You might also like