Dijkstra's Algorithm
/PROGRAM FOR DIJKSTRA'S ALGORITHM
#include <stdio.h>
#include <conio.h>
#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))
int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j;
or 0 if there is no direct connection */
long d[GRAPHSIZE];
/* d[i] is the length of the shortest path between the source (s) and node i */
int prev[GRAPHSIZE]; /* prev[i] is the node that comes right before i in
the shortest path from the source to i*/
void printD() {
int i;
printf("Distances:\n");
for (i = 1; i <= n; ++i)
printf("%d\t", i);
printf("\n");
for (i = 1; i <= n; ++i) {
printf("%ld\t", d[i]);
}
printf("\n");
}
/* Prints the shortest path from the source to dest.
* dijkstra(int) MUST be run at least once BEFORE this is called */
void printPath(int dest) {
if (prev[dest] != -1)
printPath(prev[dest]);
printf("%d ", dest);
}
void dijkstra(int s) {
int i, k, mini;
int visited[GRAPHSIZE];
for (i = 1; i <= n; ++i) {
d[i] = INFINITY;
prev[i] = -1; /* no path has yet been found to i */
visited[i] = 0; /* the i-th element has not yet been visited */
}
d[s] = 0;
for (k = 1; k <= n; ++k) {
mini = -1;
for (i = 1; i <= n; ++i)
if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
mini = i;
visited[mini] = 1;
for (i = 1; i <= n; ++i)
if (dist[mini][i])
if (d[mini] + dist[mini][i] < d[i])
{
d[i] = d[mini] + dist[mini][i];
prev[i] = mini;
}
}
}
void main() {
int i, j;
int u, v, w;
//clrscr();
FILE *fin = fopen("dist.txt", "r");
fscanf(fin, "%d", &e);
for (i = 0; i < e; ++i)
for (j = 0; j < e; ++j)
dist[i][j] = 0;
n = -1;
for (i = 0; i < e; ++i) {
fscanf(fin, "%d%d%d", &u, &v, &w);
dist[u][v] = w;
n = MAX(u, MAX(v, n));
}
fclose(fin);
dijkstra(1);
printD();
printf("\n");
for (i = 1; i <= n; ++i) {
printf("Path to %d: ", i);
printPath(i);
printf("\n");
}
getch();
}
/*SAMPLE OUTPUT
____________________
inputfile: dist.txt
10
1 2 10
1 4 5
2 3 1
2 4 3
3 5 6
4 2 2
4 3 9
4 5 2
5 1 7
5 3 4
_____________________
OUTPUT
Distances:
1 2 3 4 5
0 7 8 5 7
Path to 1: 1
Path to 2: 1 4 2
Path to 3: 1 4 2 3
Path to 4: 1 4
Path to 5: 1 4 5
*/
Distance Vector Routing Algorithm
//PROGRAM FOR DISTANCE VECTOR ROUTING ALGORITHM
#include<stdio.h>
#include<conio.h>
struct node
{
unsigned dist[20];
unsigned from[20];
}rt[10];
int main()
{
int dmat[20][20];
int n,i,j,k,count=0;
printf("\nEnter number of nodes : ");
scanf("%d",&n);
printf("\nEnter the cost matrix :\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d",&dmat[i][j]);
dmat[i][i]=0;
rt[i].dist[j]=dmat[i][j];
rt[i].from[j]=j;
}
do
{
count=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
if(rt[i].dist[j]>dmat[i][k]+rt[k].dist[j])
{
rt[i].dist[j]=rt[i].dist[k]+rt[k].dist[j];
rt[i].from[j]=k;
count++;
}
}while(count!=0);
for(i=0;i<n;i++)
{
printf("\n\nNODE %d ROUTING TABLE",i+1);
printf("\nNode\tDistance\tViaNode\n");
for(j=0;j<n;j++)
{
printf("\t\n %d\t %d\t\t %d",j+1,rt[i].dist[j],rt[i].from[j]+1);
}
}
printf("\n\n");
return 0;
getch();
}
/*SAMPLE OUTPUT
**********INPUT*********
Enter number of nodes : 5
Enter the cost matrix :
0 4 2 6 99
4 0 99 99 99
2 99 0 3 99
6 99 3 0 2
99 99 99 2 0
::::::OUTPUT :::::
NODE 1 ROUTING TABLE
Node Distance ViaNode
1 0 1
2 4 2
3 2 3
4 5 3
5 7 4
NODE 2 ROUTING TABLE
Node Distance ViaNode
1 4 1
2 0 2
3 6 1
4 9 1
5 11 1
NODE 3 ROUTING TABLE
Node Distance ViaNode
1 2 1
2 6 1
3 0 3
4 3 4
5 5 4
NODE 4 ROUTING TABLE
Node Distance ViaNode
1 5 3
2 9 1
3 3 3
4 0 4
5 2 5
NODE 5 ROUTING TABLE
Node Distance ViaNode
1 7 4
2 11 4
3 5 4
4 2 4
5 0 5
No comments:
Post a Comment