implement three graphing methods we have discussed in class. Prim’s Algorithm to
ID: 3599766 • Letter: I
Question
implement three graphing methods we have discussed in class. Prim’s Algorithm to find the minimum spanning tree in a weighted graph, Kruskall’s Algoritm to find the minimum spanning tree for a weighted graph, and Floyd-Warshall’s Algorithm to find the length of the shortest path between all pair of vertices in a weighted connected simple graph.
For Prim’s and Kruskal’s part of the assignment you will need to do some research to find the pseudocode to implement.
Below is some guidance for Floyd-Warshall’s algorithm.
You should display your output step by step as you change values in the adjacency matrix. A sample of what should be printed appears below.
Here is pseudocode for Floyd-Warshall’s algorithm :
BEGIN
for each vertex v
d[v][v] 0
for each edge (u,v)
d[u][v] w(u,v)
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if d[i][j] > d[i][k] + d[k][j]
d[i][j] d[i][k] + d[k][j]
end if
END
Note the colors are not necessary to display in the console. They are just added here to show what is changing at each step.
The initial matrix is as follows:
a b c d e
a 0 50 80
b 0 60 90
c 0 40
d 20 0 70
e 50 0
The final matrix is as follows:
a b c d e
a 0 50 100 80 140
b 0 60 90 100
c 90 0 180 40
d 110 20 0 60
e 50 110 140 0
Explanation / Answer
Floyd Warshell in java -
import java.util.*;
import java.lang.*;
import java.io.*;
class AllPairShortestPath
{
final static int INF = 99999, V = 5;
void floydWarshall(int graph[][])
{
int dist[][] = new int[V][V];
int 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++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][])
{
System.out.println("Following matrix shows the shortest "+
"distances between every pair of vertices");
for (int i=0; i<V; ++i)
{
for (int j=0; j<V; ++j)
{
if (dist[i][j]==INF)
System.out.print("INF ");
else
System.out.print(dist[i][j]+" ");
}
System.out.println();
}
}
public static void main (String[] args)
{
int graph[V][V] = { {0, 50, INF, 80 , INF},
{INF, 0, 60 , 90 , INF},
{INF, INF, 0 ,INF , 40},
{INF, INF, 20, 0 , 70},
{INF, 50 , INF, INF, 0}
};
AllPairShortestPath a = new AllPairShortestPath();
// Print the solution
a.floydWarshall(graph);
}
}
Prims using Java -
import java.util.*;
import java.lang.*;
import java.io.*;
class MST
{
private static final int V=5;
int minKey(int key[], Boolean mstSet[])
{
int min = Integer.MAX_VALUE, min_index=-1;
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 n, int graph[][])
{
System.out.println("Edge Weight");
for (int i = 1; i < V; i++)
System.out.println(parent[i]+" - "+ i+" "+
graph[i][parent[i]]);
}
void primMST(int graph[][])
{
int parent[] = new int[V];
int key[] = new int [V];
Boolean mstSet[] = new Boolean[V];
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++)
{
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
key[0] = 0; // Make key 0 so that this vertex is
// picked as first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V-1; count++)
{
int u = minKey(key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v]!=0 && mstSet[v] == false &&
graph[u][v] < key[v])
{
parent[v] = u;
key[v] = graph[u][v];
}
}
// print the constructed MST
printMST(parent, V, graph);
}
public static void main (String[] args)
{
MST t = new MST();
int graph[][] = new int[][] {{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},
};
t.primMST(graph);
}
}
//java program for Kruskal's
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph
{
class Edge implements Comparable<Edge>
{
int src, dest, weight;
public int compareTo(Edge compareEdge)
{
return this.weight-compareEdge.weight;
}
};
class subset
{
int parent, rank;
};
int V, E; // V-> no. of vertices & E->no.of edges
Edge edge[]; // collection of all edges
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[E];
for (int i=0; i<e; ++i)
edge[i] = new Edge();
}
int find(subset subsets[], int i)
{
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// If ranks are same, then make one as root and increment
// its rank by one
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// The main function to construct MST using Kruskal's algorithm
void KruskalMST()
{
Edge result[] = new Edge[V]; // Tnis will store the resultant MST
int e = 0; // An index variable, used for result[]
int i = 0; // An index variable, used for sorted edges
for (i=0; i<V; ++i)
result[i] = new Edge();
Arrays.sort(edge);
// Allocate memory for creating V ssubsets
subset subsets[] = new subset[V];
for(i=0; i<V; ++i)
subsets[i]=new subset();
// Create V subsets with single elements
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0; // Index used to pick next edge
// Number of edges to be taken is equal to V-1
while (e < V - 1)
{
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
}
System.out.println("Following are the edges in " +
"the constructed MST");
for (i = 0; i < e; ++i)
System.out.println(result[i].src+" -- " +
result[i].dest+" == " + result[i].weight);
}
public static void main (String[] args)
{
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
Graph graph = new Graph(V, E);
// add edge 0-1
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 14;
// add edge 0-2
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 6;
// add edge 0-3
graph.edge[2].src = 0;
graph.edge[2].dest = 3;
graph.edge[2].weight = 5;
// add edge 1-3
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 15;
// add edge 2-3
graph.edge[4].src = 2;
graph.edge[4].dest = 3;
graph.edge[4].weight = 4;
graph.KruskalMST();
}
}
// C Program for Floyd Warshall Algorithm
#include<stdio.h>
// Number of vertices in the graph
#define V 5
#define INF 99999//Define Infinite as a large enough value.
// A function to print the solution matrix
void printSolution(int dist[][V]);
// Solves the all-pairs shortest path problem using Floyd Warshall algorithm
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++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printSolution(dist);
}
void printSolution(int dist[][V])
{
printf ("Following matrix shows the shortest distances"
" between every pair of vertices ");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf(" ");
}
}
int main()
{
int graph[V][V] = { {0, 50, INF, 80 , INF},
{INF, 0, 60 , 90 , INF},
{INF, INF, 0 ,INF , 40},
{INF, INF, 20, 0 , 70},
{INF, 50 , INF, INF, 0}
};
// Print the solution
floydWarshall(graph);
return 0;
}
// A C for Prim's Minimum Spanning Tree (MST) algorithm.
#include <stdio.h>
#include <limits.h>
#define V 5//// Number of vertices in the graph
int minKey(int key[], int mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == 0 && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
// function to print the constructed MST stored in parent[]
int printMST(int parent[], int n, int graph[V][V])
{
printf("Edge Weight ");
for (int i = 1; i < V; i++)
printf("%d - %d %d ", parent[i], i, graph[i][parent[i]]);
}
void primMST(int graph[V][V])
{
int parent[V]; // Array to store constructed MST
int key[V]; // Key values used to pick minimum weight edge in cut
int mstSet[V]; // To represent set of vertices not yet included in MST
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] =0;
// Always include first 1st vertex in MST.
key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V-1; count++)
{
int u = minKey(key, mstSet);
mstSet[u] = 1;
for (int v = 0; v < V; v++)
{
if (graph[u][v] && mstSet[v] == 0&& graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
}
// print the constructed MST
printMST(parent, V, graph);
}
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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.