다익스트라 C언어 코드

2023.02.28  최초 작성

 

 

#include <stdio.h>
#define NUM_MAX 5
#define INF 1000

int arr[5][5] = {
	{0,2,3,10,INF},
	{2,0,INF,3,INF},
	{3,INF,0,3,INF},
	{10,3,3,0,1},
	{INF,INF,INF,1,0}
};

int confirm[5];
int minCost[5];

int getMinCostNode() {
	int min = INF;
	int node = 0;
	for (int i = 0; i < NUM_MAX; i++) {
		if (minCost[i] < min && !confirm[i]) {
			min = minCost[i];
			node = i;
		}
	}
	return node;
}

void dijkstra(int start) {
	for (int i = 0; i < NUM_MAX; i++) {
		minCost[i] = arr[start][i];
	}
	confirm[start] = 1;
	int loop = NUM_MAX - 1;
	while (loop--) {
		int current = getMinCostNode();
		confirm[current] = 1;
		for (int j = 0; j < 5; j++) {
			if (!confirm[j]) {
				if (minCost[current] + arr[current][j] < minCost[j]) {
					minCost[j] = minCost[current] + arr[current][j];
				}
			}
		}
	}
}
int main(void) {
	dijkstra(0);
	for (int i = 0; i < NUM_MAX; i++) {
		printf("%d ", minCost[i]);
	}
}

[실행 결과]

0 2 3 5 6

 

 

728x90

반응형