본문 바로가기
Network

[C Network Programming] Dijkstra's Routing Algorithm C code

by TYB 2024. 3. 11.
반응형
#include<stdio.h>
#include<conio.h>
#define STRANGER 9999
#define MAX 10
#pragma warning (disable:4996)

void dijkstra(int G[MAX][MAX], int n, int startnode);

int main()
{
	int G[MAX][MAX], i, j, n, u;
	printf("\nEnter the 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", &G[i][j]);

	printf("\nEnter the starting node:");
	scanf("%d", &u);
	dijkstra(G, n, u);

	return 0;
}

void dijkstra(int G[MAX][MAX], int n, int startnode)
{

	int cost[MAX][MAX], distance[MAX], neighbor[MAX];
	int visited[MAX], count, mindistance, nextnode, i, j;

	//neighbor[] stores the neighbor of each node
	//count gives the number of nodes seen so far
	//create the cost matrix
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (G[i][j] == 0)
				cost[i][j] = STRANGER;
			else
				cost[i][j] = G[i][j];

	//initialize neighbor[],distance[] and visited[]
	for (i = 0; i < n; i++)
	{
		distance[i] = cost[startnode][i];
		neighbor[i] = startnode;
		visited[i] = 0;
	}

	distance[startnode] = 0;
	visited[startnode] = 1;
	count = 1;

	while (count < n - 1)
	{
		mindistance = STRANGER;

		//nextnode gives the node at minimum distance
		for (i = 0; i < n; i++)
			if (distance[i] < mindistance && !visited[i])
			{
				mindistance = distance[i];
				nextnode = i;
			}

		//check if a better path exists through nextnode			
		visited[nextnode] = 1;
		for (i = 0; i < n; i++)
			if (!visited[i])
				if (mindistance + cost[nextnode][i] < distance[i])
				{
					distance[i] = mindistance + cost[nextnode][i];
					neighbor[i] = nextnode;
				}
		count++;
	}

	//print the path and distance of each node
	for (i = 0; i < n; i++)
		if (i != startnode)
		{
			printf("\nDistance of node%d=%d", i, distance[i]);
			printf("\nPath=%d", i);

			j = i;
			do
			{
				j = neighbor[j];
				printf("<-%d", j);
			} while (j != startnode);
		}
}

 

반응형