[알고리즘] 최단 경로 Dijkstra

치치·2025년 1월 28일
알고리즘

알고리즘C++

목록 보기
20/24
post-thumbnail

다익스트라 알고리즘

  • 시작점으로부터 모든 노드까지의 최소 거리를 구해주는 알고리즘이다
  • "한 노드에서 다른 노드로 가는 경로의 최소 비용"
    -> 최단 경로의 기준은 무조건 시작노드이다
    (다른 한 정점에서 한 정점까지의 경로가 최단경로가 아닌 것)
    (시작 노드 -> 다른 모든 정점 까지의 경로가 최단 경로)
  • 음수 가중치를 가지지 않는다
  • 사이클을 포함하지 않는 경로만 고려한다

진짜 기억해두자!!!
결과값으로 나온 각 정점마다의 최단 경로는 시작점을 기준으로 나온 값임!!!!

최소 비용을 구하는 알고리즘에는 다익스트라 외에도 벨만-포드, 플로이드 워셜이 있다



처음 다익스트라 알고리즘의 개념에 대해 공부할때 헷갈렸던 점이 있다
-> 최소신장트리랑 다익스트라의 차이점이 뭘까?
최소신장트리도 제일 낮은 가중치부터 더해가는 거고, 다익스트라도 제일 최단 경로를 구하는 거 아닌가?

최소 신장 트리 vs 다익스트라

쉽게 말하자면 서로의 개념은 연결과 경로이다

  • 최소 신장 트리
    모든 노드를 연결하는 트리를 만들고, 그 간선들의 가중치가 최소가 되도록 하는 것
    -> 사이클x, 모든 정점을 포함하면서 연결이 된다

  • 다익스트라
    도착 정점 뿐 아니라, 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾는다
    -> 노드를 연결하는 것이 아니고 그냥 최단 경로만 찾는 것


다익스트라 과정 (그림)

  1. 그래프는 인접행렬로 구성하였다
    인접행렬 안에 각 정점들을 연결한 간선의 가중치를 저장해두었다
  • 각 노드의 방문을 확인하는 방문배열
  • 각 최단거리를 저장할 거리 배열
  • 초기셋팅에서는 값을 모두 INF 로 초기화 해둔다 (무한) -> 아직 접근을 안했기 때문
  1. 첫번째 반복
    생성자에서 초기화 한 값을 시작 정점과 연결된 간선의 거리 배열로 덮어쓴다
    현재 방문되지 않았고, 가중치가 가장 작은 인덱스는 [3]이다
    [4],[5]의 distance값이 INF인 이유는, 현재 정점1에서 직접적으로 접근할 수 없기 때문이다
    방문배열[3]을 방문체크 해주고, 인접한 정점들의 가중치를 갱신시켜줘야한다
  • 2번째 그림을 보면 정점4와 연결된 정점2의 가중치를 본다
    -> 기존 1 -> 2 까지의 가중치는 2였다
    -> 정점 4를 거쳐가는 가중치는 1 + 2다
    -> 기존이 더 짧기 때문에 갱신 할 필요 없다

2-1. 첫번째 그림에서 4와 연결된 정점 3을 보면
-> 기존 가중치 1 -> 3은 5였다
-> 정점 4를 거쳐가는 가중치는 1+ 3이다
-> 거리를 갱신하여준다
즉, 노드 1에서 노드3까지 가는 최소 거리가 4가 되는 것!!! 짧아졌다!!!

2-2. 두번째 그림에서 4와 연결된 정점5을 보자
-> 기존의 노드1에서 직접적으로 접근할 수 없어 INF값을 가진 상태이다
-> 새로 접근하는 거리의 값은 1 + 1로 2이다
-> 거리를 갱신하여준다

인접한 노드들을 다 방문했으면 다음 반복으로 넘어간다

  1. 두번째 반복
    최소값 인덱스가 2개지만, 더 작은 인덱스를 기준으로 하기 때문에 [1] 인덱스 방문체크
    앞에 과정과 동일하게 기존의 배열 값과 새로운 거리 값을 비교한다
    -> 2번에서 3번 노드로 가는 거리 값을 4로 갱신했다
    -> 여기서 노드2를 거쳐가는 방식의 거리값은 4보다 더 길다
    -> 즉, 최단거리가 아니기 때문에 갱신하지 않는다

  2. 세번째 반복
    앞의 과정과 동일하다

  3. 네번째 반복

  4. 마지막 다섯번째 반복 (SIZE - 1)
    방문하지 않은 노드 중 최솟값을 찾는 Find 함수에서 마지막 남은 노드 6을 찾고 방문체크한다
    더이상 인접한 노드가 없기 때문에 조건문을 다 건너뛰고 종료한다


단계별 코드

  1. 그래프 생성
  • 배열의 크기를 잡아줄 SIZE와 INF(무한)을 미리 정의해둠
  • 노드 방문을 체크할 방문배열
  • 최단 경로를 담아줄 거리배열
  • 인접행렬을 사용하여 그래프 내의 간선 정보를 모두 담아주었다
    ( 서로 직접적으로 접근할 수 없으면 INF로 정의)
  1. 생성자에서 방문배열, 거리배열 초기화
  2. 다익스트라 알고리즘
  • 시작 정점과 인접한 노드의 간선 정보(인접행렬로 저장해둔 것)를 거리배열에 담기
  • 시작 정점 방문체크
  • SIZE - 1만큼 반복하는데, Find함수를 사용하여 거리 배열에 들어있는 가중치 중 최소값의 인덱스를 찾아낸다
  • 최소값이 들어있는 위치를 방문 체크
  • 최소값이 들어있는 정점에 방문하지 않은 인접한 노드가 있다면, 그 노드까지의 기존 거리와 (현재 최소값 위치의 거리 + 최소값위치에서 인접한 노드까지의 거리) 값을 비교
  • 더 짧은 거리로 갱신

    3-1. 반복을 끝마치고, 거리 배열에 들어있는 값을 출력
    출력된 값이 시작노드로 부터 각 노드까지의 최단경로이다
  1. 거리 배열의 최소값의 인덱스를 찾는 Find함수
    방문되지 않은 노드이고, 반복을 돌리면서 최소수치를 가진 인덱스를 찾아서 인덱스 값을 반환
  2. 메인함수에서 객체를 생성하고 다익스트라 호출


다익스트라 과정 요약

시작점으로부터 모든 노드까지의 최소 거리를 구해주는 알고리즘이다

  1. distance 배열에 weight[시작점 노드]의 값들로
    초기화합니다.

  2. 시작점을 방문 처리합니다.

  3. distance 배열에서 최소 비용 노드를 찾고 방문 처리합니다.
    단, 이미 방문한 노드는 제외합니다.

  4. 최소 비용 노드를 거쳐갈 지 생각해서 distance 배열을 갱신합니다.
    단, 이미 방문한 노드는 제외합니다.

  5. 모든 노드를 방문할 때까지 3번 ~ 4번을 반복합니다.

방문하지 않은 노드 중에서 가장 적은 distance를 가진 노드를 방문하고, 그 노드와 연결된 다른 노드까지의 거리를 계산합니다


전체 코드

#include <iostream>
#define SIZE 6
#define INF 10000000
using namespace std;

// INF -> 무한대
// 1. 방문체크 배열 (T/F)
// 2. 가중치(거리) 배열 -> 1. 해당 정점과 연결된 거리 넣어주기(배열 크기만큼 다)
//						 2. 방문체크 해주기(해당 정점)
// 3. 인접행렬

class Graph
{
private:
	bool visited[SIZE]; // 방문 배열 (T/F)

	int distance[SIZE]; // 최단경로를 담을 거리 배열

	// 인접행렬, 각 정점을 기준으로 가중치 설정
	int weight[SIZE][SIZE] =
	{
		{0,    2,   5,   1,   INF,  INF},
		{2,    0,   3,   2,   INF,  INF},
		{5,    3,   0,   3,     1,    5},
		{1,    2,   3,   0,     1,  INF},
		{INF,INF,   1,   1,     0,    2},
		{INF,INF,   5, INF,     2,    0}
	};


public:
	Graph()
	{
		for (int i = 0; i < SIZE; i++)
		{
			visited[i] = false;
			distance[i] = INF;
		}
	}

	void Dijkstra(int start)
	{
		// 생성자에 초기화 한 값을 덮어씀
		// 1. 시작 정점과 연결된 간선을 거리 배열에 넣어주기 
		for (int i = 0; i < SIZE; i++)
		{
			distance[i] = weight[start][i];
			//cout << distance[i] << " ";
		}
		// 2. 방문체크
		visited[start] = true;


		for (int i = 0; i < SIZE - 1; i++)
		{
			// 3. 거리 배열 내에서 최소값의 인덱스를 찾음 (정점)
			int minNode = Find();

			// 4. 최소값의 인덱스 방문체크
			visited[minNode] = true;

			// 5. 최소값의 정점과 연결된 정점까지의 최소거리 갱신 
			for (int j = 0; j < SIZE; j++)
			{
				if (visited[j] == false)
				{
					// 기존에 저장된 거리 배열보다 새 거리가 더 짧으면 갱신
					if (distance[minNode] + weight[minNode][j] < distance[j])
					{
						distance[j] = distance[minNode] + weight[minNode][j];
					}
				}
			}
		}

		cout << "각 정점마다 도달할 수 있는 최단 거리 : " << endl;
		for (int i = 0; i < SIZE; i++)
		{
			cout << "정점["<< i << "] : " << distance[i] << endl;
		}
	}

	// 배열의 최솟값의 인덱스를 찾는 함수
	const int& Find()
	{
		int position = 0;
		int min = INF;

		// 방문체크 되지않은 정점 탐색
		for (int i = 0; i < SIZE; i++)
		{
			if (distance[i] < min && visited[i] == false)
			{
				min = distance[i];
				position = i;
			}
		}
		return position;
	}
};


int main()
{
#pragma region 다익스트라 알고리즘
	
	Graph graph;

	graph.Dijkstra(0);

#pragma endregion




	return 0;
}

결과값:
결과값을 보면 시작 정점이었던 1을 기준으로 모든 정점까지의 최단 경로가 완성되었다


다익스트라 시간복잡도

최단거리 저장을 배열로 했을 경우

  • 가장 짧은 간선을 찾는 과정은 Find함수를 사용함
    -> Find함수를 사용한다
    -> 배열의 크기가 정점의 갯수(V)와 동일하기 때문에 한 정점에 방문하여 확인할때마다
    V개를 V번 반복한다 = V²

    즉, 한 정점을 고를때마다 그 정점과 인접한 간선들을 다 갱신한 뒤, 그 배열 안에서 짧은 간선을 찾는 과정 (Find)를 V번 수행하고, 모든 정점을 다 확인하기 때문에 V번 반복하는 것

  • 간선 거리를 비교하고 갱신하는 과정
    -> 각 간선을 한번씩만 확인하기 때문에 간선 수 만큼 E
    -> 이미 방문한 노드의 간선은 확인하지 않기 때문이다

배열로 저장했을때의 시간복잡도

O(V² + E)
V : 정점의 수
E : 간선의 수


다익스트라 코드 다시보기

#include <iostream>
#define SIZE 6
#define INF 1000000
using namespace std;

class Graph
{
private:
	bool visited[SIZE];  // 1. 방문 배열

	int distance[SIZE];   // 2. 거리 배열(최소 가중치를 저장 - 계속 갱신)

	int weight[SIZE][SIZE] = // 3. 그래프 인접행렬 (각 간선 정보를 저장)
	{
		{ 0,    6,  3, INF, INF, INF },
		{ 6,    0,  2,   5, INF, INF },
		{ 3,    2,  0,   3,   4, INF },
		{ INF,  5,  3,   0,   2,   3 },
		{ INF,INF,  4,   2,   0,   5 },
		{ INF,INF,INF,   3,   5,   0 }
	};
 
public:
	// 생성자에서 값 초기화
	Graph()
	{
		for (int i = 0; i < SIZE; i++)
		{
			visited[i] = false;
			distance[i] = INF;
		}
	}

	void Dijkctra(int start)
	{
		for (int i = 0; i < SIZE; i++)
		{
			// 1. 거리 배열에 시작점을 기준으로 노드의 가중치 저장
			distance[i] = weight[start][i];
		}
		visited[start] = true; // 2. 방문체크

		for (int i = 0; i < SIZE - 1; i++)
		{
			// 3. 거리배열에서 방문체크 안된 노드 중 가장 최솟값 찾기
			int minNode = Find();

			visited[minNode] = true; // 4. 찾은 노드 방문체크
	
			for (int j = 0; j < SIZE; j++)
			{
				if (visited[j] == false)
				{
					if (distance[j] > distance[minNode] + weight[minNode][j]) 
					{
						// 5. 거리 배열 값을 갱신
						distance[j] = distance[minNode] + weight[minNode][j];
					}
				}
			}
		}

		cout << "시작점으로 부터 각 노드까지의 최단 경로 : ";
		for (int i = 0; i < SIZE; i++)
		{
			cout << distance[i] << " ";
		}
	}	

	int Find()
	{
		int position = 0; // 최소값 인덱스를 담을 변수
		int min = INF; // 최소값 갱신용

		for (int i = 0; i < SIZE; i++)
		{
			if (visited[i] == false && min > distance[i])
			{
				min = distance[i]; // 최소값 갱신
				position = i; // 인덱스 갱신
			}
		}
		return position;
	}

};


int main()
{
	Graph graph;

	graph.Dijkctra(0);

	return 0;
}
  • 방문체크가 되지 않은 노드들만 조건문(거리 배열 갱신)을 실행하는 이유
    -> 방문된 노드는 이미 최단 거리가 확정된 상태
    -> 연산해도 최단 거리는 변하지 않기 때문에, 불필요한 작업이다

결과값:

profile
치치
뉴비 개발자
이전 포스트

[알고리즘] Minimum Spanning Tree

다음 포스트

알고리즘 복습

1개의 댓글

comment-user-thumbnail
JSH1C
2025년 1월 29일

최고야!

답글 달기