현제 방문하지 않는 노드중에 최소 거리인 노드를 찾기 위해 순차탐색을 사용할 수 있습니다.

• 이때 시간복잡도는 O(N^2)입니다.
• 총 O(N)번에 걸쳐 선형탐색합니다.

의사코드

#include <vector>
// 아직 방문하지 않은 노드 중
// 가장 거리값이 작은 노드의 인덱스 반환
int FindSmallestNode(){
	int min_dist = INF;
	int min_idx = -1;
	for (int i = 0; i<= N; i++){
		if (visited[i] == true) continue;
		if (dist[i] < min_dist){
			min_dist = dist[i];
			min_idx = i;
		}
	}
	return min_idx;
}

// 다익스트라
void Dijkstra(){
	for (int i = 1; i <= N; i++) dist[i] = map[start][i];  // 시작 노드와 인접한 정점에 대해 거리 계산
	dist[start] = 0;
	visited[start] = true;

	for (int i = 0; i < N - 1; i++){
		int new_node = FindSmallestNode();
		visited[new_node] = true;

		for(int j = 0; j <= N; j++){
			if (visited[j] == true)continue;
			if (dist[j] > dist[new_node] + map[new_node][j]) dist[j] = dist[new_node] + map[new_node][j];
		}
	}
}

최소 힙과의 차이점?

기본적으로 순차탐색으로 최소 거리 노드를 찾기 때문에 전체 노드 갯수가 5000개만 넘어서도 효율이 좋지 않습니다. 이때 최소 힙( 우선순위 큐라고도 불립니다 ) 을 이용하면 더 효율적으로 최단 경로를 찾을 수 있습니다.