Course Code: CSE2202
Course Title: Algorithms Lab
Complex Engineering Project
Submitted to:
Course Teacher: Sabrina Jesmin
Submitted by:
Name: Natasha Bose (211014015)
Name: Tarek Mahamud Rashik(203014021)
Name: Md. Nur Hasan Masum (203014011)
Name: Jaima Tasnim (212014023)
Department of CSE
Fall’2022
University of Liberal Arts Bangladesh
Objective/Problem Statement
The shortest path that will be used by a student to travel from their residence to Ulab
permanent campus.
Resources
CodeBlocks/Replit/ VsCode
The algorithmic approach we have selected for the project is Prim’s Algorithm. Prim’s
algorithm falls under the section of greedy algorithms; it selects a local optimum in
hopes to reach a value of global optimum. The working of prim’s is that it starts from
a single node and moves through several adjacent nodes to traverse all of the
connected edges along the way.
Our aim is to find the shortest path from the residence to Ulab. Along the path there
are many nodes which we have to visit to reach our final destination. Suppose a
student has to visit his friend’s home, then gym, then his part time job site and lastly
reach Ulab. We have to find the path with the minimum cost while travelling to these
nodes along the way.
Logic:
Step 1: Select a starting vertex.
Step 2: Repeat Steps 3 and 4 until there are fringe vertices.
Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has
minimum weight.
Step 4: Add the selected edge and the vertex to the minimum spanning tree T.
Step 5: [END OF LOOP].
Step 6: EXIT.
Time complexity:
We delete the V vertex from the Min-Heap because we have V vertices in the graph,
and each iteration deletes 1 edge, for a total of V-1 edges in MST, with a complexity
of O(log(V)). And we add up to E edges altogether, with each addition having a
complexity of O(log(V)). As a result,
the total complexity is O((V+E)Log(V)).
Sample Input(s)
Enter the number of nodes:5
Enter the adjacency matrix:
0 10 20 30 40
10 0 10 20 30
20 10 0 10 20
30 20 10 0 10
40 30 20 10 0
Source Code
#include<stdio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
printf("\nEnter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
while(ne < n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]< min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0){
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
}
Generated Output(s)
Discussion
In computer science, Prim's algorithm is a greedy algorithm that finds a minimum
spanning tree for a weighted undirected graph. This means it finds a subset of the
edges that forms a tree that includes every vertex, where the total weight of all the
edges in the tree is [Link] time complexity of the Prim's Algorithm is O ( ( V
+ E ) l o g V ) because each vertex is inserted in the priority queue only once and
insertion in priority queue take logarithmic time.