[TIL] 알고리즘 : 그래프 (3)

그래프 이전 내용

https://lullu-nan-potato-developer.tistory.com/8

[TIL] 알고리즘 : 그래프

https://lullu-nan-potato-developer.tistory.com/10

[TIL] 알고리즘 : 그래프 (2)

 

오늘은 그래프 마지막 이론 .. ! 낼부터는 DP다 무서워라잉

 

8. 최단경로 찾기

- 종류

1. BFS 완전 탐색 알고리즘 : 가중치 없거나 모든 가중치(음수x)가 같을때
2. 다익스트라 Dijkstra 알고리즘 : 음이 아닌 가중치
3. 벨만-포드-무어 Bellman-Ford-Moore 알고리즘 : 가중 그래프 ( 음수도 가능. 타임머신! ) 
4. 플로이드-워셜 Floyd-Warshall 알고리즘 : 전체 쌍 (모든 정점에서 모든 정점으로)

2~4에 대해, 시간복잡도 & 커버 범위 : 2<3<4

 

• 단일 출발 / 단일 도착 / 단일쌍 최단경로 : 간선의 비용에 따라 다익스트라, 벨만포드무어 中 선택
• 전체 쌍 최단경로 : 플로이드워셜

 

9. 다익스트라 알고리즘

: V개의 정점과, 음수가 아닌 E개의 간선을 가진 가중 그래프 G에서, 특정 출발 정점에서 다른 모든 정점까지의 최단경로 구하는 알고리즘

- 특징

• 각 정점을 최대 한번씩만 방문하며 최단거리 확장함 (음의 가중치 아니어야 알고리즘 동작)
• 아직 방문하지 않은 정점들 중 최단거리인 점을 찾아 방문하여 최단거리를 확정함. => 이를 반복
• 시간복잡도 O(nlgn) : n개의 노드 방문 * 한개의 노드 방문하는데 걸리는 시간 lgn (우선순위큐/최소힙 사용)
• 최단거리가 최소인 정점 찾는 과정은 '우선순위 큐/ 최소힙'으로 구현해야 효율적임을 명심
• 왜냐면, 최소힙 삽입삭제 시간복잡도 : lgN
• 간선 관련해서는 vector에 넣어두고 하나씩 꺼내가며 정점들 연결해보쟈~~

 

참고) 백준 - 최단 경로 (1753)

#include<cstdio>
#include<climits>//INT_MAX
#include<vector>
#include<queue>
int V, E, K;
struct n_t { //node
	inline bool operator < (const n_t& ref) const { //c++에서는 heap 기본으로 maxheap 사용
		return this->cost > ref.cost; //cost 작은걸
	}
};
std::vector<n_t> AL[20001];
int visited[20001]; //각 정점에 대한 최단 경로 비용을 저장 (매우 큰 값인경우 미방문)

int main() {
	scanf("%d %d", &V, &E);
	scanf("%d", &K);
	for (int i = 0; i < E; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		AL[u].push_back({ v,w }); //make_pair(v,w)로 하지 않아도 초기화 가능. pair 초기화 키워드로 찾아보기
	}
	for (int i = 1; i <= V; i++) visited[i] = INT_MAX;

	// Dijkstra
	std::priority_queue<n_t> PQ;
	visited[K] = 0;
	PQ.push({ K,0 });
	while (!PQ.empty()) {
		n_t curr = PQ.top();
		PQ.pop();
		for (n_t next : AL[curr.node]) {
			int cost = visited[curr.node] + next.cost;
			if (cost < visited[next.node]) { //미방문 정점 확인
				visited[next.node] = cost; //좀더 최적화를 위한것임. 굳이 안해도됨
				//방문했을때 갱신하는게 아니라, 방문할 예정일때 visited에 묻혀놓기 
				//-> pq에 의미없는 값이 들어가는것과 판단 로직 횟수를 경감해줌
				PQ.push({ next.node,cost });
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		if (visited[i] == INT_MAX)
			puts("INF");
		else printf("%d\n", visited[i]);
	}
}

 

10. 벨만 - 포드 - 무어 알고리즘

: V개의 정점과 E개의 간선을 가진 가중 그래프 G에서, 특정 출발 정점에서 다른 모든 정점까지의 최단경로 구하는 알고리즘. 음수의 가중치도 허용함

- 특징

• 음의 가중치를 갖는 간선도 가능
• 음의 사이클 존재 여부 확인 가능
• 시간복잡도 O(n^2) : 연산 n*n
• int visited[] :최단 cost 저장용
• 그래프 표현방식 : 간선리스트(간선표)를 사용. 인접리스트x ( c++에서 이차원 배열, 구조체 등으로 구현 )
• 보통 유향 그래프에서도 사용가능한 개념이나, '음수 가중치'만은 단방향으로 구성되어야함.

 

- 방법

1. 최단거리 구하기 : V-1번 E개의 모든 간선 및 가중치를 확인한다
2. 음의 사이클 존재 여부를 확인하기 위해, 한번더 E개의 간선 및 가중치를 확인한다
3. V번째(step2) 확인 과정 중, 거리 비용 배열이 갱신된다면 그래프 G는 음의 사이클을 가진다

 

참고) 백준 - 타임머신 (11657)

#include<cstdio>
#include<climits>//INT_MAX
long long visited[500 + 1]; //cost 저장용 150억까지 커버할 수 있게끔 (간선 서로 같은 음수 가중치일때..?)
//시작점과 도착점을 연결하는 간선이 하나가 아니고, ~~한 경우가 있을수있으므로.. 이거 캐치가 포인트
int edgeList[3][6000 + 1]; //간선리스트
int N, M, A, B, C;

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) { //간선리스트에 간선 정보저장
		scanf("%d %d %d", &A, &B, &C);
		edgeList[0][i] = A;
		edgeList[1][i] = B;
		edgeList[2][i] = C;
	}
	visited[1] = 0;
	for (int i = 2; i <= N; i++) {
		visited[i] = INT_MAX;
	}

	for (int i = 1; i <= N - 1; i++) {
		for (int j = 1; j <= M; j++) {
			if (visited[edgeList[0][j]] != INT_MAX) {
				if (visited[edgeList[1][j]] > visited[edgeList[0][j]]+ edgeList[2][j]) {
					visited[edgeList[1][j]] = visited[edgeList[0][j]] + edgeList[2][j];
				}
			}
		}
		//if(visited[i])
	}
	
	for (int j = 1; j <= M; j++) {
		if (visited[edgeList[0][j]] != INT_MAX) {
			if (visited[edgeList[1][j]] > visited[edgeList[0][j]] + edgeList[2][j]) {
				visited[edgeList[1][j]] = visited[edgeList[0][j]] + edgeList[2][j];
				printf("-1\n");
				return 0;
			}
		}
	}
	for (int i = 2; i <= N; i++) {
		if (visited[i] == INT_MAX) {
			printf("-1\n");
		}
		else {
			printf("%lld\n", visited[i]);
		}
	}
}

 

11. 플로이드 - 워셜 알고리즘

: V개의 정점과 E개의 간선을 가진 가중 그래프 G에서, 모든 정점 사이의 최단경로 구하는 알고리즘.

- 특징

• 순환만 없다면, 음수 가중치 가능
• if 음수 사이클 있다면 -> 플로이드 워셜 그래프의 최단거리 배열 대각선을 0이 아닌 음수로 설정
• 기본적으로, DP방식으로 접근함
• 처음 인접 행렬 -> 경유지에 2번노드 추가 될 때 -> 경유지에 3번노드 추가 될 때 -> ... -> 경유지에 n번 노드 추가될 때
• 최단거리 저장을 위해 주로 인접 행렬 사용. 무한대에서 시작, 노드 추가될 때 마다 최단경로 유의미하면 갱신
• 시간복잡도 O(n^3) : 각 노드 인접행렬 n^2 * 이 과정 n번

 

참고) 백준 - 플로이드 (11404)

#include <cstdio>
const int INF = 1987654321;
inline int MIN(int a, int b) { return a < b ? a : b; }
int N, M; //N: 정점 ~100, M: 간선갯수 ~100000
//인접행렬 --> 최단경로의 비용들이 저장되는곳
int AM[101][101];
int main() {
	scanf("%d %d", &N, &M);
	//초기화
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i != j) AM[i][j] = INF;
		}
	}

	//간선 정보 받기
	for (int i = 0; i < M; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		AM[a][b] = MIN(AM[a][b], c);
	}

	//플로이드 워셜 돌리기
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				AM[i][j] = MIN(AM[i][j], AM[i][k] + AM[k][j]);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%d ", AM[i][j] == INF ? 0 : AM[i][j]);
		}
		puts(""); //문자열 출력후 줄바꿈
	}
}

 

절대 끝나지 않을것같던 이론이 ~.. 어느새 DP만을 남겨뒀구 .. 하핫 얼마 안남은만큼 더더욱 홧팅!