[이코테/C++] 7. 최단 경로 알고리즘

목차

출처
개념
특징
로직
예제문제

 

---

출처

이것이 코딩테스트다

(이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘

---

 

개념

최단경로

• 분류 : 다이나믹 프로그래밍
• 가능한 문제상황
  • 한 지점 → 다른 한 지점
  • 한 지점 → 다른 모든 지점
  • 모든 지점 → 다른 모든 지점
• 각 지점 = 노드
• 지점 간 연결된 도로 = 간선

 

다익스트라 Dijkstra

분류: 그리디. 매 상황에서 가장 비용이 적은 노드 선택

특정 노드에서 출발 → 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘

'음의 간선'이 없을 때 정상 작동

자기자신: 길이=0

 

다익스트라 - 우선순위 큐 : C++의 heap은 최대힙이므로 데이터를 꺼내거나 입력할 때는 음수(-)로 넣어서 최소힙으로 동작하도록 만듦

 

다익스트라 - 로직

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. (방문하지 않은 노드 중) 최단 거리인 노드를 선택
4. 출발 노드 → 3번에서 선택한 노드의 거리 비용 계산하여 최단 거리 테이블 갱신
5. 목적지까지 3~4번 반복

---

플로이드 워셜 Floyd Warshall

분류 : 다이나믹 프로그래밍

모든 노드에서 다른 모든 노드까지의 최단 경로를 계산

vs 다익스트라) 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾지 X

2차원 테이블에 최단 거리 정보 저장

 

플로이드 워셜 -  점화식

(a → b로 가는 최단 거리) vs (a → k → b로 가는 최단 거리) 

$ D_{ab} = min(D_{ab}, D_{ak}+D_{kb}) $

 

플로이드 워셜 - 로직

[초기 상태]
1. 그래프 준비
2. 그래프 정보에 따라 최단 거리 테이블 초기화
- 전부 무한으로 초기화
- 자기자신 → 자기자신 : 0으로 초기화
-  start → end : 그래프의 간선 정보로 초기화

[갱신]
1. 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신
(1번노드를 거쳐가는 경우 : 2 → 1 → 3 / 2 → 1 → 4 / 3→ 1 → 2 등)
2. 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신
3. 3번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신
4. 4번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신

 

 

시간 복잡도

다익스트라 - 기본 로직 : $ O\left ( V^{2} \right ) $

 

다익스트라 - 우선순위 큐 : $ O\left ( E lg(V) \right ) $

※ E = 최대 간선의 개수(우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 횟수)

※ V = 노드의 개수

 

플로이드 워셜 :  $ O\left ( V^{3} \right ) $

※ 삼중 반복문이라서

※ V = 노드의 개수(500개가 최대)

노드나 간선의 개수가 많을 수록 다익스트라가 유리

---

구현

다익스트라

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

#define INF 1e9

using namespace std;

const int MAX = 100001;

// 노드 개수, 간선 개수
int n, m, start{};

// 노드 정보를 담은 배열
vector<pair<int, int>> graph[MAX];

// 최단거리 테이블
int dis[MAX];

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq;

	// 시작 노드로 가기 위한 최단 경로는 0으로 설정. 큐에 삽입
	pq.push({ 0, start });
	dis[start] = 0;

	while (!pq.empty()) {
		// 가장 최단 거리가 짧은 노드 꺼내기
		int nowCost = -pq.top().first; // 현재 노드까지의 비용 (최소힙으로 동작하려면 음수(-)로 넣어야함)
		int nowNode = pq.top().second; // 현재 노드
		pq.pop();

		// 현재 노드가 이미 처리된 거면 무시
		if (dis[nowNode] < nowCost) continue;

		// 현재 노드와 연결된 다른 인접 노드들 확인
		for (int i = 0; i < graph[nowNode].size(); i++) {
			// 현재 노드를 거쳐서 갈 때의 비용
			int cost = nowCost + graph[nowNode][i].second;

			// cost가 더 최단 거리라면 업데이트
			int nextNode = graph[nowNode][i].first;
			if (cost < dis[nextNode]) {
				dis[nextNode] = cost;
				pq.push(make_pair(-cost, nextNode)); // (최소힙으로 동작하려면 음수(-)로 넣어야함)
			}
		}
	}
}

int main() {
	cin >> n >> m >> start;

	// 모든 간선 정보를 입력받기
	for (int i = 0; i < m; i++) {
		int nowNode, nextNode, cost;
		cin >> nowNode >> nextNode >> cost;
		graph[nowNode].push_back({ nextNode, cost });
	}

	// 최단 거리 테이블을 모두 무한으로 초기화
	fill(dis, dis + MAX, INF);

	// 다익스트라
	dijkstra(start);

	// 모든 노드로 가기 위한 최단 거리 출력
	for (int i = 1; i <= n; i++) {
		// 도달 못하면 INF 출력
		if (dis[i] == INF) cout << "INF\n";
		else cout << dis[i];
	}

}

 

플로이드 워셜

#include<iostream>
#include<vector>
#include<algorithm>

#define INF = 1e9

using namespace std;

const int MAX = 500;

int v, e; // 노드의 개수, 간선의 개수

// 그래프 : 2차원 배열
int graph[MAX+1][MAX+1]

int main(){
	cin >> v >> e;
    
    // [초기상태]
    // 최단 거리 테이블을 모두 무한으로 초기화
    for(int i = 0; i < MAX+1; i++){
    	fill(graph[i], graph[i] + MAX + 1, INF);
    }

	// 자기 자신 → 자기 자신 : 비용 0
    for(int i = 1; i <= v; i++){
    	for(int j = 1; j <= v; j++){
        	if(i == j) graph[i][j] = 0;
        }
    }
    
    // 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
    for(int i = 0; i < e; i++){
    	// start → end : 비용 cost
        int start, end, cost;
        cin >> start >> end >> cost;
        graph[start][end] = cost;
    }
	
    // [갱신]
    // 점화식에 따라 플로이드 워셜 알고리즘 수행
    for(int k = 1; k <= v; k++){
    	for(int start = 1; start <= v; start++){
        	for(int end = 1; end <= v; end++){
            	graph[start][end] = min(graph[start][end], graph[start][k]+graph[k][end]);
            }
        }
    }
    
    // 수행 결과 출력
    for(int i = 1; i <= v; i++){
    	for(int j = 1; j <= v; j++){
        	if(graph[i][j] == INF) cout << "INFINITY ";
            else cout << graph[i][j] << " ";
        }
        cout << "\n";
    }
}

 

 

---

예제 문제

-와 유사한 문제들

[백준]

1753 최단경로

 

[프로그래머스]

배달

등산코스 정하기

 

[백준-데이크스트라]

[백준-플로이드워셜]