Algorithm 최단 경로 문제

황상진·2022년 6월 27일

algorithm 최단거리

Algorithm

목록 보기

5/8

최단 경로 문제 Algorithm

최단 경로 문제

최단거리 문제는 자주 나오지는 않지만 주요 기업에서 한번씩 나온다

최단 경로 알고리즘은 강장 짧은 경로를 찾는 알고리즘

BFS - 모든 간선의 비용이 동일할 때(단순 큐)
Dijkstra - 한지점에서 다른 모든 지점
Floyd Warshald - 모든 지점에서 다른 모든 지점
Bellman-Ford - 한 지점에서 다른 모든 지점 + 음의 간선

문제 예시

https://www.acmicpc.net/step/26

https://www.acmicpc.net/problem/11404 플로이드
https://www.acmicpc.net/problem/1753 최단 경로
https://www.acmicpc.net/problem/1162 도로포장
https://www.acmicpc.net/problem/1504 특정한 최단 경로
https://www.acmicpc.net/problem/9370 미확인 도착지
https://www.acmicpc.net/problem/5719 거의 최단 경로
https://www.acmicpc.net/problem/2325 개코전쟁

Dijkstra

특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
음의 간선이 없을 때 정상 작동 -> 음의 간선이 포함될 때는 Bellman-ford 알고리즘
다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류

매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

동작 과정

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

특징

그리디 알고리즘
단계를 거치며 한 번 처리된 노드의 최단 거리는 고정
다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단거리 정보가 저장

인접 리스트 - 간선의 개수에 비례하는 메모리만 차지, ij가 연결되었는지 확인 여부 O(V), 연결된 모든 노드를 방문할 경우 O(V)보다 작거나 같다
인접 행렬 - 구현이 쉽다,ij가 연결되었는지 확인 여부 O(1) 시간 복잡도, 연결된 모든 노드를 방문할 경우 O(V)

우선순위 큐를 이용한 Dijkstra

void Dijkstra() {
	//최단 거리 테이블 초기화
	for (int i = 1; i <= V; i++) {
		res[i] = INF;
	}

	priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    //출발 노드 설정
	pq.push({ 0,K });
	res[K] = 0;

	while (!pq.empty()) {
		auto t = pq.top();
		pq.pop();
		int dist = t.first;
		int now = t.second;

		for (auto i : m[now]) {
			int cost = dist + i.second;
			int next = i.first;

			if (cost < res[next]) {
				res[next] = cost;
				pq.push({ cost,next });
			}
		}
	}
}