GRAPH ALGORITHMS : FLOYD-WARSHAL -Displaying DISTANCE MATRIX and PI MATRIX using C PROGRAM

Modify the following Floyd-Warshall algorithm by introducing a π(pi) table as per the class’s discussion. Here you can write one function named as generatePiTable(int g[][V])

                                .....................................................................................

                               

#include <stdio.h>

#define V 4

#define INF 99999

#define NIL 0

void warshallAlgo(int g[][V]){

    int i,j,k;

    for(k=0;k<V;k++){

        for(i=0;i<V;i++){

            for(j=0;j<V;j++){

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

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

                }

            }

        }

    }

    printSols(g);

    generatePiTable(g);

}

void printSols(int g[][V]){

    printf("The matrix for shortest distance: \n");

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

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

            if(g[i][j]==INF){

                printf("%5s","INF");

            }

            else{

                printf("%5d",g[i][j]);

            }

        }

        printf("\n");

    }

}

void generatePiTable(int g[][V]){

    printf("\nThe pi table is as follows: \n");

    int pi[V][V];

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

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

            if(g[i][j]==NIL || g[i][j]==INF){

                pi[i][j]=NIL;

            }

            else{

                pi[i][j]=i+1;

            }

        }

    }

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

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

            if (pi[i][j] == INF || pi[i][j] == NIL){

                printf("%5s","NIL");

            }

            else{

                printf("%5d",pi[i][j]);

            }

        }

        printf("\n");

    }

}

int main(){

    int g[V][V];

    printf("Enter the graph: \n");

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

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

            scanf("%d",&g[i][j]);

        }

    }

    warshallAlgo(g);

    return 0;

}

BRANCH AND BOUND : C CODE for JOB ASSIGNMENT PROBLEM

C code to solve JOB ASSIGNMENT problem using Branch and Bound.

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#define MAX_JOBS 10

int costMatrix[MAX_JOBS][MAX_JOBS];

int numJobs;

int minCost = INT_MAX;

int bestAssignment[MAX_JOBS];

void branchAndBound(int assignment[MAX_JOBS], int numAssigned, int costSoFar)

{

 if (numAssigned == numJobs) {

 // All jobs have been assigned, so update the best assignment if the current cost is lower

 if (costSoFar < minCost) {

 minCost = costSoFar;

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

 bestAssignment[i] = assignment[i];

 }

 }

 } else {

 // Assign the next job to each available worker and branch on the resulting cost

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

 if (assignment[i] == -1) {

 // This job has not been assigned yet

 int newAssignment[MAX_JOBS];

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

 newAssignment[j] = assignment[j];

 }

 newAssignment[i] = numAssigned;

 int newCost = costSoFar + costMatrix[numAssigned][i];

 if (newCost < minCost) {

 // Only explore this branch if it could potentially lead to a better solution

 branchAndBound(newAssignment, numAssigned + 1, newCost);

 }

 }

 }

 }

}

int main()

{

 // Read input from file or user input

 printf("Enter the number of jobs: ");

 scanf("%d", &numJobs);

 printf("Enter the cost matrix:\n");

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

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

 scanf("%d", &costMatrix[i][j]);

 }

 }

 // Initialize the assignment to all unassigned

 int assignment[MAX_JOBS];

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

 assignment[i] = -1;

 }

 // Solve the problem using branch and bound

 branchAndBound(assignment, 0, 0);

 // Print the best assignment and its cost

 printf("Best assignment: ");

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

 printf("(%d, %d) ", bestAssignment[i], i);

 }

 printf("\nCost: %d\n", minCost);

 return 0;

}

GRAPH ALGORITHMS : C PROGRAM for FORD-FULKERSON maximum flow ALGORITHM with User Input

 FORD-FULKERSON maximum flow ALGORITHM with User Input

 #include <stdio.h>

#define A 0

#define B 1

#define C 2

#define MAX_NODES 1000

#define O 1000000000

int n;

int e;

int capacity[MAX_NODES][MAX_NODES];

int flow[MAX_NODES][MAX_NODES];

int color[MAX_NODES];

int pred[MAX_NODES];

int min(int x, int y) {

return x < y ? x : y;

}

int head, tail,top;

int q[MAX_NODES + 2];

int path[MAX_NODES];

void enqueue(int x) {

q[tail] = x;

tail++;

color[x] = B;

}

int dequeue() {

int x = q[head];

head++;

color[x] = C;

return x;

}

void push(int x){

path[top]=x;

top++;

}

int pop(){

int output = path[top];

top--;

return output;

}

// Using BFS as a searching algorithm

int bfs(int start, int target) {

int u, v;

for (u = 0; u < n; u++) {

color[u] = A;

}

head = tail = 0;

enqueue(start);

pred[start] = -1;

while (head != tail) {

u = dequeue();

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

if (color[v] == A && capacity[u][v] - flow[u][v] > 0) {

enqueue(v);

pred[v] = u;

}

}

}

return color[target] == C;

}

void residual_graph(){

int i,j;

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

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

if(capacity[i][j]!=0){

printf("\n%d - %d capacity left: %d",i,j,capacity[i][j]-

flow[i][j]);

if((capacity[i][j]-flow[i][j])==0)

printf(" Path is blocked");

}

}

}

}

// Applying fordfulkerson algorithm

int fordFulkerson(int source, int sink) {

int i, j, u;

int max_flow = 0;

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

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

flow[i][j] = 0;

}

}

// Updating the residual values of edges

while (bfs(source, sink)) {

int increment = O;

for (u = n - 1; pred[u] >= 0; u = pred[u]) {

increment = min(increment, capacity[pred[u]][u] -

flow[pred[u]][u]);

}

top=0;

for (u = n - 1; pred[u] >= 0; u = pred[u]) {

push(u);

flow[pred[u]][u] += increment;

flow[u][pred[u]] -= increment;

}

push(u);

// Adding the path flows

max_flow += increment;

printf("\nPath chosen: ");

pop();

while(top>=0){

printf("%d ",pop());

}

residual_graph();

printf("\n");

}

return max_flow;

}

int main() {

int start,end,c,source,sink,i,j;

printf("Enter number of vertices: \n");

scanf("%d",&n);

printf("Enter number of edges: \n");

scanf("%d",&e);

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

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

capacity[i][j] = 0;

}

}

//int i;

for(i=1;i<=e;i++){

printf("Enter start vertex,end vertex and capacity for edge %d\n",i);

scanf("%d%d%d",&start,&end,&c);

capacity[start][end] = c;

}

printf("\n Enter source and sink vertices\n");

scanf("%d%d",&source,&sink);

printf("Max Flow: %d\n", fordFulkerson(source, sink));

}

    

GRAPH ALGORITHMS : C PROGRAM for BELLMANFORD DETECTING negative(-ve) CYCLE WITH USER INPUT

 C PROGRAM TO IMPLEMENT BELLMANFORD DETECTING -VE CYCLE WITH USER INPUT 

 #include <stdio.h>

#include <stdlib.h>

#define INFINITY 99999

struct Edge {

    int u;

    int v;

    int w;

};

struct Graph {

    int V;

    int E;

    struct Edge *edge;

};

void bellmanford(struct Graph *g, int source);

void display(int arr[], int size);

int main(void){

int i;

    struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph));

    printf("Enter number of edges : ");

    scanf("%d",&g->E);

    printf("\nEnter number of vertices : ");

    scanf("%d",&g->V);

    g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge));

    for(i=0;i<g->E;i++){

        printf("Enter vertices and weight value of edge %d : ",i+1);

        scanf("%d %d %d",&g->edge[i].u,&g->edge[i].v,&g->edge[i].w);

    }

    bellmanford(g, 0);

    return 0;

}

void bellmanford(struct Graph *g, int source) {

    int i, j, u, v, w;

    int tV = g->V;

    int tE = g->E;

    int d[tV];

    int p[tV];

    for (i = 0; i < tV; i++) {

        d[i] = INFINITY;

        p[i] = 0;

    }

    d[source] = 0;

    for (i = 1; i <= tV - 1; i++) {

        for (j = 0; j < tE; j++) {

            u = g->edge[j].u;

            v = g->edge[j].v;

            w = g->edge[j].w;

            if (d[u] != INFINITY && d[v] > d[u] + w) {

                d[v] = d[u] + w;

                p[v] = u;

            }

        }

    }

    for (i = 0; i < tE; i++) {

        u = g->edge[i].u;

        v = g->edge[i].v;

        w = g->edge[i].w;

        if (d[u] != INFINITY && d[v] > d[u] + w) {

            printf("Negative weight cycle detected!");

            printf("Edge value are %d %d %d",u,v,w);

            return;

        }

    }

    printf("Distance array: ");

    display(d, tV);

    printf("Predecessor array: ");

    display(p, tV);

}

void display(int arr[], int size) {

    int i;

    for (i = 0; i < size; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

}

Output : 

EXCERCISE PROBLEM: STRING MACHINE AND NETWORK FLOW