Practical No-12

Aim: Write a program to find shortest paths in a graph with arbitrary edge weights using
Bellman-Ford’s algorithm.

Source Code:
#include <bits/stdc++.h>
struct Edge {
int src, dest, weight;
};
struct Graph* createGraph(int V, int E){
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];

for (int i = 1; i <= V - 1; i++) {

for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;} }
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return; // If negative cycle is detected, simply return } }
printArr(dist, V);}
int main()
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);

graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;

31
 graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;

graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;

graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;

graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;

graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;

BellmanFord(graph, 0);

return 0;
}

Output:

32
 Practical No-13
Aim: Write a program to find shortest paths in a graph with arbitrary edge weights using
Flyod’s algorithm.

Source Code:

#include <bits/stdc++.h>

using namespace std;

#define V 4

#define INF 99999

void printSolution(int dist[][V]);

void floydWarshall(int graph[][V])

int dist[V][V], i, j, k;

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

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

dist[i][j] = graph[i][j];

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

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

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

if (dist[i][j] > (dist[i][k] + dist[k][j])

&& (dist[k][j] != INF

&& dist[i][k] != INF))

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

printSolution(dist); }

void printSolution(int dist[][V]){

cout << "The following matrix shows the shortest "

"distances"

" between every pair of vertices \n";

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

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

if (dist[i][j] == INF)

cout << "INF"

<< " ";

else

cout << dist[i][j] << " ";

cout << endl;

int main()

int graph[V][V] = { { 0, 5, INF, 10 },

{ INF, 0, 3, INF },

{ INF, INF, 0, 1 },

{ INF, INF, INF, 0 } };

floydWarshall(graph);

return 0;

Output:

34
 Practical No-14
Aim: Write a program to find the minimum spanning tree in a weighted, undirected graph using
Prim’s algorithm.

Source Code:
#include <bits/stdc++.h>
using namespace std;
#define V 5
int minKey(int key[], bool mstSet[])
{
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;

return min_index;
}

void printMST(int parent[], int graph[V][V])

{
cout<<"Edge \tWeight\n";

for (int i = 1; i < V; i++)

cout<<parent[i]<<" - "<<i<<" \t"<<graph[i][parent[i]]<<" \n";
}

void primMST(int graph[V][V])

{
int parent[V];
int key[V];
bool mstSet[V];

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

key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1; // First node is always root of MST

for (int count = 0; count < V - 1; count++)

{
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}

printMST(parent, graph);

35
}

int main()
{

int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };

// Print the solution

primMST(graph);

return 0;
}

Output:

36
 Practical No-15

Aim: Write a program to find the minimum spanning tree in a weighted, undirected graph using
Kruskal’s algorithm.

Source Code:
#include <bits/stdc++.h>
using namespace std;

#define V 5
int parent[V];

// Find set of vertex i

int find(int i)
{
while (parent[i] != i)
i = parent[i];
return i;
}
void union1(int i, int j)
{
int a = find(i);
int b = find(j);
parent[a] = b;
}

// Finds MST using Kruskal's algorithm

void kruskalMST(int cost[][V])
{
int mincost = 0; // Cost of min MST.

// Initialize sets of disjoint sets.

for (int i = 0; i < V; i++)
parent[i] = i;
int edge_count = 0;
while (edge_count < V - 1) {
int min = INT_MAX, a = -1, b = -1;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (find(i) != find(j) && cost[i][j] < min) {
min = cost[i][j];
a = i;
b = j;
}
}
}

union1(a, b);
37
 printf("Edge %d:(%d, %d) cost:%d \n",
edge_count++, a, b, min);
mincost += min;
}
printf("\n Minimum cost= %d \n", mincost);
}

// driver program to test above function

int main()
{
/* Let us create the following graph
2 3
(0)--(1)--(2)
| /\ |
6| 8/ \5 |7
|/ \|
(3)-------(4)
9 */
int cost[][V] = {
{ INT_MAX, 2, INT_MAX, 6, INT_MAX },
{ 2, INT_MAX, 3, 8, 5 },
{ INT_MAX, 3, INT_MAX, INT_MAX, 7 },
{ 6, 8, INT_MAX, INT_MAX, 9 },
{ INT_MAX, 5, 7, 9, INT_MAX },
};

// Print the solution

kruskalMST(cost);

return 0;
}

Output:

38