Design Analysis and Algorithm
(PCCCS 494)
Department Name : Computer Science and Engineering
Name : Tiasa Biswas
Roll No. : 25300119036
Assignment – 7
PROBLEM STATEMENT:
Write a program to implement DIJKSTRA’s ALGORITHM .
ALGORITHM:
1 Declaring: function 'Dijkstra' of type void with 'int Graph[MAX][MAX], int n, int start' params
1.1 Declaring: cost[n][n], dist[n], pred[n] of type int
1.2 Declaring: visited[n], count, mindist, nextnode, i, j of type int
1.3 ITERATING i = 0 while i < n
1.3.1 ITERATING j = 0 while j < n
1.3.1.1 CHECK IF Graph[i][j] == 0
1.3.1.1.1 cost[i][j]=9999
[End of if]
1.3.1.2 ELSE
1.3.1.2.1 cost[i][j]=Graph[i][j]
[End of else]
[End of for]
[End of for]
1.4 ITERATING i = 0 while i < n
1.4.1 dist[i]=cost[start][i]
1.4.2 pred[i]=start
1.4.3 visited[i]=0
[End of for]
1.5 dist[start]=0
1.6 visited[start]=1
1.7 count=1
1.8 ITERATE WHILE count < n
1.8.1 mindist=9999
1.8.2 ITERATING i = count while i < n
1.8.2.1 CHECK IF dist[i] < mindist && !visited[i]
1.8.2.1.1 mindist=dist[i]
1.8.2.1.2 nextnode=i
[End of if]
[End of for]
1.8.3 visited[nextnode]=0
1.8.4 ITERATING i = count while i < n
1.8.4.1 CHECK IF !visited[i]
1.8.4.1.1 CHECK IF mindist + cost[nextnode][i] < dist[i]
1.8.4.1.1.1 dist[i]=mindist + cost[nextnode][i]
1.8.4.1.1.2 pred[i]=nextnode
[End of if]
[End of if]
[End of for]
[End of while]
1.9 ITERATING i = 0 while i < n
1.9.1 CHECK IF i != start
1.9.1.1 PRINT i+1, dist[i], i+1
1.9.1.2 j=i
1.9.1.3 ITERATE Do loop
1.9.1.3.1 j=pred[j]
1.9.1.3.2 PRINT j+1
[End of if]
1.9.1.4 ITERATE WHILE j != start
[End of while]
[End of for]
[End of Dijkstra]
2 Declaring: function 'main' of type int
2.1 Initializing: i, j, n, u = 0 of type int
2.2 PRINT "Enter no.of vertices:\n"
2.3 INPUT n,
2.4 Declaring: Graph[MAX][MAX] of type int
2.5 PRINT "Enter elements of adjacency matrix:\n"
2.6 ITERATING i = 0 while i < n
2.6.1 ITERATING j = 0 while j < n
2.6.1.1 INPUT Graph[i][j],
[End of for]
2.6.2 PRINT "\n"
[End of for]
2.7 Calling: function 'Dijkstra' with 'Graph, n, u' args
[End of main]
SOURCE CODE:
#include <stdio.h>
#define MAX 10
void Dijkstra (int Graph[MAX][MAX], int n, int start)
int cost[n][n], dist[n], pred[n];
int visited[n], count, mindist, nextnode, i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (Graph[i][j] == 0)
cost[i][j] = 9999;
else
cost[i][j] = Graph[i][j];
}
}
for (i = 0; i < n; i++)
dist[i] = cost[start][i];
pred[i] = start;
visited[i] = 0;
dist[start] = 0;
visited[start] = 1;
count = 1;
while (count < n)
mindist = 9999;
for (i = count; i < n; i++)
if (dist[i] < mindist && !visited[i])
mindist = dist[i];
nextnode = i;
visited[nextnode] = 0;
for (i = count; i < n; i++)
if (!visited[i])
if (mindist + cost[nextnode][i] < dist[i])
{
dist[i] = mindist + cost[nextnode][i];
pred[i] = nextnode;
count++;
for (i = 0; i < n; i++)
if (i != start)
printf ("\nDist from src to %d: %d\nPath from src : %d", i+1, dist[i], i+1);
j = i;
do
j = pred[j];
printf (" <-- %d", j+1);
while (j != start);
int main ()
int i, j, n, u = 0;
printf ("Enter no.of vertices:\n");
scanf ("%d", &n);
int Graph[MAX][MAX];
printf ("Enter elements of adjacency matrix:\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf ("%d", &Graph[i][j]);
printf ("\n");
Dijkstra (Graph, n, u);
OUTPUT:
Enter no.of vertices:
Enter elements of adjacency matrix:
0 3 6 9999 9999 9999 9999
3 0 2 4 9999 9999 9999
6 2 0 1 4 2 9999
9999 4 1 0 2 9999 4
9999 9999 4 2 0 2 1
9999 9999 2 9999 2 0 1
9999 9999 9999 4 1 1 0
Dist from src to 2: 3
Path from src : 2 <-- 1
Dist from src to 3: 5
Path from src : 3 <-- 2 <-- 1
Dist from src to 4: 6
Path from src : 4 <-- 3 <-- 2 <-- 1
Dist from src to 5: 8
Path from src : 5 <-- 4 <-- 3 <-- 2 <-- 1
Dist from src to 6: 7
Path from src : 6 <-- 3 <-- 2 <-- 1
Dist from src to 7: 8
Path from src : 7 <-- 6 <-- 3 <-- 2 <-- 1
[Program finished]
