[Algorithm] 최단경로 알고리즘 모음 (다익스트라, 벨만-포드, 플로이드-워셜)

Algorithm

[Algorithm] 최단경로 알고리즘 모음 (다익스트라, 벨만-포드, 플로이드-워셜)

young_3060 2023. 11. 30. 01:27

728x90

🚦 이번 포스팅에서는 〰️

▶️ 최단 경로 알고리즘?
▶️ 주요 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜)
▶️ 다익스트라 알고리즘
▶️ 벨만-포드 알고리즘
▶️ 플로이드-워셜 알고리즘

이번에는 최단 경로 알고리즘을 싹다 정리해보기로 했다!!

마침, 너무 정리가 잘 된 블로그를 찾게되어서 블로그 글을 요약해보며 공부하기로 했다. 블로그 = https://roytravel.tistory.com/340

감사합니다.

📌 최단 경로 알고리즘?

: 최단 경로 문제는 가중 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다.

〰️ 최단 경로 계산 방식

One-To-One
: 한 지점에서 다른 특정 지점까지의 최단경로
One-To-All
: 한 지점에서 다른 모든 지점까지의 최단경로
All-To-All
: 모든 지점에서 모든 지점까지의 최단경로

📌 주요 알고리즘들(다익스트라, 벨만-포드, 플로이드-워셜)

BFS(완전 탐색) 알고리즘
: 가중치가 없거나, 모든 가중치가 같은 경우 가장 빠름
Dijkstra(다익스트라) 알고리즘
: 음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단경로 문제, One-To-All
Bellman-Ford(벨만-포드) 알고리즘
: 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단경로 문제
Floyd-Warshall(플로이드-워셜) 알고리즘
: 전체 All-To-All 문제

BFS는 이전에 이미 다뤘기 때문에 여기선 넘어가겠다!

BFS가 궁금하다면? >> BFS(너비 우선 탐색)이란? 참고

📌 Dijkstra(다익스트라) 알고리즘

: 개발된지는 좀 됐지만 지금까지도 대부분의 경우에 적용되는 알고리즘!

특정 노드에서 출발해 다른 모든 노드로 가는 각각의 최단경로를 구한다.

BUT 모든 간선의 가중치는 양의 정수여야 한다

✅ 다익스트라는 그리디와 동적계획법이 합쳐진 형태이다.

✅ 현재 위치한 노드에서 최선의 경로를 반복적으로 찾으며, 이전에 계산해둔 경로를 활용하여 중복된 하위 문제를 풀기 때문이다.

✅ 시간복잡도 = O((V+E)logV)

💡 다익스트라의 모든 간선이 양의 가중치를 가져야하는 이유

: 그리디를 통해 최단 경로라고 여겨진 값을 DP 테이블에 저장한 뒤, 재방문하지 않는데, 만약 음의 가중치가 있다면 이러한 규칙이 어긋날 수 있기 때문이다.

=> 음의 가중치가 포함되는 경우, 플로이드-워셜이나 벨만-포드 알고리즘을 사용한다. (시간복잡도가 늘어나는 단점)

왜 음의 가중치가 있으면 안되는데?

사실 그냥 음의 가중치가 있다면 큰 문제는 안되지만, 그래프에 사이클이 있는 경우 문제가 생긴다.

만일, 이런 사이클을 가진 그래프에서 다익스트라 알고리즘을 이용하여 최단 경로를 구한다고 가정하자.

이 경우, 1번->4번의 최소비용은 12이다. 하지만, 중간에 사이클이 있기 때문에, 3번->4번에서 넘어가지 못하고 가중치 4와 가중치 -6이 무한 반복되며 테이블이 갱신될 것이다. (값은 무한히 작아짐)

〰️ 동작 방식

출발 노드 설정, 최단 거리 테이블 초기화
방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택
해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 갱신
반복한다.

말은 어려우니까, 예제와 함께 정확한 과정을 이해해보자.

다음은 초기 DP 테이블이다.

node	1	2	3	4	5
1	0	3	INF	8	9
2	3	0	2	INF	INF
3	INF	2	0	1	3
4	8	INF	1	0	INF
5	9	INF	3	INF	0

IF) 노드 1을 선택했을때

1과 연결된 3개의 간선을 확인한다. 이 중 최소비용을 낼 수 있는 2번 노드로 이동하고 1번 노드는 방문처리한다.

테이블 값의 변화는 없다.

[1번 노드의 테이블 값]

INF

2번 노드로 이동했다. 2번노드에 연결된 노드는 1번, 3번이지만 이미 1번은 방문처리가 되었으므로 자동으로 노드 3으로 이동한 후, 2번을 방문처리해준다.

이때! 테이블 값에는 변화가 있다. 1번과 3번은 연결되지 않았었지만, 계속해서 최적의 상태를 업데이트 하다가(그리디) 3번을 방문할 수 있기 때문에, 비용을 업데이트 해준다. (2+3 = 5)

이제 3번노드로 왔다. 3번 노드에 연결된 것은 2번, 4번, 5번이지만 2번은 이미 방문했으므로 넘어간다. 4번과 5번 중 가중치가 더 적은 것은 4번이기 때문에, 4번으로 이동하고 3번은 방문처리 해준다.

테이블 값의 변화가 있다. 기존 1->4 비용은 8이었지만, 1->2->3->4의 비용은 6이므로 6으로 업데이트 해준다.

이제 4번 노드에 도착했다. 4번노드에 연결된 것은 3번과 1번이지만 두개의 노드는 이미 방문했으므로, 알고리즘이 여기서 끝나게 된다.

따라서 1번노드에서 다른 모든 노드까지의 최종 비용은 다음과 같다.

이 과정을 코드로 구현하려면 가중치의 중요도를 고려하여 자료구조 힙, 즉 "우선순위 큐"를 사용하여 구현한다.

<코드>

vector<pair<int,int> > node[N];
int dist[N]; //dist는 INF로 초기화 필요

void Dijkstra_Heap()
{
	//최소
	priority_queue<pair<int,int>, greater<int> > pq;
    pq.push(make_pair(0, start)); //시작노드는 가중치 0
    
    //dist[start] = 0은 시작점~노드(시작점)까지 가는데 비용이 0이다.
    dist[start] = 0; //거리 저장, start==0
    
    while(!pq.empty())
    {
    	int cost = pq.top().first; //가중치
        int cur = pq.top().second; //노드번호
        pq.pop();
        
        //이미 최단거리 있으면 pass
        if(dist[cur] < cost) continue;
        
        //모든 인접노드 검사 코드
        for(int i=0; i<node[cur].size(); i++) {
        	int nCost = cost + node[cur][i].first; //가중치
            int next = node[cur][i].second; //노드번호
            
            //새로운 최단거리를 찾았다면 dist 갱신 후 pq에 push
            if(dist[next] > nCost) {
            	dist[next] = nCost;
                pq.push(make_pair(dist[next], next);
            }
        }
    }
    
}

📌 Bellman-Ford(벨만-포드) 알고리즘

: 특정 노드로부터 다른 노드까지의 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘의 간선 음수 한계점을 보완한 알고리즘이다.

기본적으로 다익스트라와 동일하지만, 핵심적인 차이점은 가중치가 음수일때도 작동한다는 점이겠다.

매 단계마다 모든 간선을 전부 확인한다. 다익스트라는 출발노드에서 연결된 노드만 탐색했지만, 벨만-포드는 모든 노드가 한번씩 출발점이 되어 다른 노드까지의 최소비용을 구한다.

다만, 모든 경우의 수를 고려하는 동적 계획법이 사용되기 때문에 시간 복잡도가 늘어나는 단점이 있다.

따라서, 가중치가 모두 양수라면 다익스트라 알고리즘을 사용하도록 하자.

✅ 시간복잡도 = O(VE)

〰️ 예제와 함께 이해해보는 시간

위와 같은 그래프가 주어졌을 때, 초기의 DP 테이블은 아래와 같다.

INF

[Iteration 1]

첫번째로 노드 1번을 출발노드로 지정해본다.

-6

2번 노드로 넘어가겠다. 2번노드는 3번과 연결되어있다.

1->3 비용은 3, 1->2->3 비용은 -8으로, 후자가 더 작기때문에 DP를 3->-8로 업데이트해준다.

-6

-8

3번 노드로 넘어간다. 3번은 4번, 5번 노드와 연결되어있다. 두개 다 살펴보자.

[4번] 1->4 = 9이고, 1->2->3->4 = -3이므로, 업데이트해준다.

[5번] 1->5 = 8이고, 1->2->3->5 = -15이므로, 업데이트해준다.

-6

-8

-3

-15

4번 노드로 넘어왔다. 4번은 3번과 연결되어있다.

4->3으로 가려면 1->4->3이고 비용은 5이다. 이것은 이미 테이블에 저장된 경로인 1->2->3, 비용 -8보다 크기때문에 테이블 업데이트는 해주지 않는다.

-6

-8

-3

-15

이제 5번 노드로 왔다. 5번은 3번과 연결되어있다.

DP테이블에서 3번은 현재 1->2->3을 거친 -8이다. 1->5->3은 비용이 -5이므로 업데이트하지 않는다.

-6

-8

-3

-15

자, 이제 1번노드를 시작노드로 해서 모든 노드를 돌아보았다.

이 과정을 노드 개수(V) -1 만큼 반복 진행해준다.

💡TIP 음의 사이클 여부를 알고싶다면?

반복을 한번 더 해준다. (최종적으로 반복 수 = 노드개수 V)

왜냐하면, 한번 더 진행했을 때 값이 바뀐다면 음의 사이클이 있다는 뜻이기 때문이다. (무한히 작아짐)

최종적으로, 각 Iteration의 종료 결과는 아래와 같다.

[Iteration 1] = [INF, 0, -6, -8, -3, -15]

[Iteration 2] = [INF, 0, -6, -28, -23, -35]

[Iteration 3] = [INF, 0, -6, -48, -43, -55]

[Iteration 4] = [INF, 0 -6, -68, -63, -75]

[Iteration 5] = [INF, 0, -6, -88, -63, -75]

<코드>

vector<pair<pair<int,int>, int>> node[N];
int dist[N];

//start = 1
void bellman-ford(int start)
{
	dist[start] = 0;
    for(int i=1; i<V; i++) {
    	for(int j=0; j<node.size(); j++) {
        	int from = node[j].first.first;
            int to = node[j].first.second;
            int cost = node[j].second;
            
            if(dist[from] == INF) continue;
            if(dist[to] > dist[from] + cost) dist[to] = dist[from] + cost;
        }
    }
    
    for(int i=0; i<node.size(); i++) {
    	int from = node[i].first.first;
        int to = node[i].first.second;
        int cost = node[i].second;
        
        if(dist[from] == INF) continue;
        if(dist[to] > dist[from] + cost) {
        	cout << "음의 사이클 존재" << endl;
            return;
        }
    }
}

📌 Floyd-Warshall(플로이드-워셜) 알고리즘

: 모든 노드간의 최단 거리를 구하는 알고리즘이다. < 한 노드 -> 다른 모든 노드 > 를 구하는 다익스트라와 벨만-포드 알고리즘과의 가장 큰 차이이다. 또한, 음의 가중치가 있더라도 최단경로를 구할 수 있다. (IF) 음의 사이클이 있다면 벨만-포드 알고리즘 사용할 것!

❗️[핵심] 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. 아래는 점화식이다.

i->j로 가는 것과 i->k->j로 가는 것 중 어느 것이 최소 비용인지 찾는 식이다.

✔️ 구현도 3중 for문으로 매우 간단하게 가능하다.

✅ 모든 노드간의 최단 거리를 구할 때, 점화식이 사용되기 때문에 동적 계획법에 해당된다. (테이블 필요)

✅ 이때, 모든 노드를 다뤄야 하므로 2차원 배열이 사용된다. (다익스트라는 1차원 배열 사용)

✅ 시간 복잡도는 3중 for문 때문에 = O(N^3)

〰️ 예제와 함께 이해해보는 시간

위의 그림같은 그래프가 있을때, 초기 DP 테이블은 아래와 같다.

node	1	2	3	4
1	INF	5	INF	7
2	4	INF	-3	INF
3	6	INF	INF	4
4	INF	INF	2	INF

3중 for문을 사용해 거쳐가는 노드(k)를 설정 후, 테이블 업데이트를 해줄것이다.

먼저, 거쳐가는 노드(k)가 1일때의 경우를 보자.

[Iteration 1] 거쳐가는 노드(k) = 1

( k=1 ) : 노드 1을 거쳐 노드 1~4를 탐색하는 과정

<첫번째 행 업데이트> : 노드 1에서 노드 1을 거쳐 노드 1~4까지 탐색

graph[1][1] = min(graph[1][1], graph[1][1] + graph[1][1]) : 0 vs 0+0 = 0, 업데이트X graph[k][k] = 0

graph[1][2] = min(graph[1][2], graph[1][1] + graph[1][2]) : 5 vs 0+5 = 5, 업데이트X

graph[1][3] = min(graph[1][3], graph[1][1] + graph[1][3]) : INF vs 0+INF = INF, 업데이트X

graph[1][4] = min(graph[1][4], graph[1][1] + graph[1][4]) : 7 vs 0+7 = 7, 업데이트X

[Iteration 1]의 첫번째 행 결과 테이블

graph[k][k] = 0으로 바뀐 것만 제외하면 업데이트가 없다.

node	1	2	3	4
1	0	5	INF	7
2	4	INF	-3	INF
3	6	INF	INF	4
4	INF	INF	2	INF

<두번째 행 업데이트> : 노드 2에서 노드 1을 거쳐 노드 1~4까지 탐색

graph[2][1] = min(graph[2][1], graph[2][1] + graph[1][1]) : 4 vs 4+0 = 0, 업데이트X

graph[2][2] = min(graph[2][2], graph[2][1] + graph[1][2]) : INF vs 4+5 = 9, 업데이트O

graph[2][3] = min(graph[2][3], graph[2][1] + graph[1][3]) : -3 vs 4+INF = -3, 업데이트X

graph[2][4] = min(graph[2][4], graph[2][1] + graph[1][4]) : INF vs 4+7 = 11, 업데이트O

[Iteration 1]의 두번째 행 결과 테이블

node	1	2	3	4
1	INF	5	INF	7
2	4	9	-3	11
3	6	INF	INF	4
4	INF	INF	2	INF

<세번째 행 업데이트> : 노드 3에서 노드 1을 거쳐 노드 1~4까지 탐색

graph[3][1] = min(graph[3][1], graph[3][1] + graph[1][1]) : 6 vs 6+0 = 0, 업데이트X

graph[3][2] = min(graph[3][2], graph[3][1] + graph[1][2]) : INF vs 6+5 = 11, 업데이트O

graph[3][3] = min(graph[3][3], graph[3][1] + graph[1][3]) : INF vs 6+INF = INF, 업데이트X

graph[3][4] = min(graph[3][4], graph[3][1] + graph[1][4]) : 4 vs 6+7 = 13, 업데이트X

[Iteration 1]의 세번째 행 결과 테이블

node	1	2	3	4
1	INF	5	INF	7
2	4	INF	-3	INF
3	6	11	INF	4
4	INF	INF	2	INF

<네번째 행 업데이트> : 노드 4에서 노드 1을 거쳐 노드 1~4까지 탐색

graph[4][1] = min(graph[4][1], graph[4][1] + graph[1][1]) : INF vs INF+0 = INF, 업데이트X

graph[4][2] = min(graph[4][2], graph[4][1] + graph[1][2]) : INF vs INF+5 = INF, 업데이트X

graph[4][3] = min(graph[4][3], graph[4][1] + graph[1][3]) : INF vs INF = INF, 업데이트X

graph[4][4] = min(graph[4][4], graph[4][1] + graph[1][4]) : INF vs INF+7 = INF, 업데이트X

[Iteration 1]의 네번째 행 결과 테이블

node	1	2	3	4
1	INF	5	INF	7
2	4	INF	-3	INF
3	6	INF	INF	4
4	INF	INF	2	INF

[Iteration 1]의 과정이 끝났다! 이제 이 과정을 노드의 수만큼 반복해주면 된다.

Iteration 2는 노드 1~4에서 노드 2를 거쳐 노드 1~4를 탐색하는 경우.

Iteration 3는 노드 1~4에서 노드 3를 거쳐 노드 1~4를 탐색하는 경우.

Iteration 4는 노드 1~4에서 노드 4를 거쳐 노드 1~4를 탐색하는 경우.

<코드>

for(int k=1; k<=V; k++) {
	graph[k][k] = 0;
    for(int i=1; i<=V; i++) {
    	for(int j=1; j<=V; j++) {
        	graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
        }
    }
}

[Reference]

https://jina-developer.tistory.com/118

https://roytravel.tistory.com/340

728x90

저작자표시

'Algorithm' 카테고리의 다른 글

[Algorithm] 위상정렬(Topology Sort) (2)	2023.12.01
[Algorithm] 분할 정복(Divide&Conquer)이란? (0)	2023.11.24
[Algorithm] 백트래킹(Backtracking)이란? (2)	2023.11.24
[Algorithm] 동적 계획법(Dynamic Programming)이란? (0)	2023.08.19
[Algorithm] Greedy(탐욕) 알고리즘 (0)	2023.08.16

현재글[Algorithm] 최단경로 알고리즘 모음 (다익스트라, 벨만-포드, 플로이드-워셜)

걸음마코딩기

찾아나가는중 〰️〰️

Vector, greedy algorithm, CS, Queue, baekjoon, 프로그래머스, stack, dp, git, 경사하강법, 백준, 우선순위 큐, Algorithm, 백준 큐문제, Optimizer 종류, C++, 자료구조, 알고리즘, dynamic programming, 컴퓨터구조,

Today :
Yesterday :

걸음마코딩기