최단 경로

다익스트라 알고리즘

• 최소 비용을 구해야 할 때 사용 가능
• 한 지점에서 다른 특정 지점까지의 최단 경로 구해야 할 경우에 사용 가능
• 음의 간선이 없을 때 정상 동작함 (현실에는 음의 간선의 길이 없어서 GPS의 기본 알고리즘으로 사용됨)
• 그리디 알고리즘
  -> 매번 가장 비용이 적은 노드를 선택해 과정을 반복함

동작 원리

dist[] 에 비용 저장, INF로 초기화 되어 있음

1. 출발 노드 설정, 최단 거리 초기화 (dist[] INF로 초기화)
2. 출발 노드를 방문한 노드로 체크하기
3. 출발 노드와 연결되어 있고 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택, 방문했다고 체크
4. 이 노드에서 다른 노드로 가는 비용을 계산해 dist[] 갱신
5. 3,4 과정을 반복

구현 방법

1. 동작 원리대로 구현하기
   - 시간 복잡도가 O(V²) V은 노드 개수
   - dist[] 생성, 매 단계마다 dist[]의 모든 원소를 확인(순차 탐색) (최단 거리 가장 짧은 노드 선택하기 위해서)
2. 우선순위 큐 사용
   - 시간 복잡도 O(ElogV) V은 노드 개수, E는 간선 개수
   - 현재 가장 가까운 노드를 저장하기 위해서 우선순위 큐를 추가로 사용
   - 기본적으로 최대 힙으로 구현되어 있어서 최소힙으로 사용해야함
     1. 우선순위에 해당하는 값에 -를 붙여 넣었다가 꺼낸 후에 -를 붙여 원래 값으로 돌리는 방식 사용
     2. 최소 힙으로 선언

//1개일 때
priority_queue<int, vector<int>, greater<int>> pq;
//보통 가중치와 정점 2개로 이뤄짐
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

 

플로이드 워셜 알고리즘

• 모든 지점에서 다른 모든 지점까지의 최단 경로 모두 구해야 할 때 사용 가능
• 단계마다 '거쳐가는 노드'를 기준으로 알고리즘 수행함
• 매번 최단 거리를 갖는 노드 안 찾아도 됨
• 음의 간선 있어도 적용 가능 (음의 사이클일 경우 제외)
• dp 알고리즘
• 시간 복잡도 O(N³)

동작 원리

• N*N 크기의 dist[] - 각각의 노드가 다른 노드로 가는데 필요한 비용 (i부터 j까지, 대각선이 0)
• i번째 노드에 대해 dist[i][i] < 0 일 때 음의 사이클 발생한 것

1. dist[] 배열을 만들고 초기화함 (연결된 노드끼리의 비용 채우고 없으면 INF, 대각선은 0)
2. 거쳐가는 정점 (순서대로 함) 정한 후 dist[] 갱신하기
   (x->y 최소비용) vs (x->정점 + 정점->y)
3. 2번의 과정을 N번만큼 반복

구현 방법

동작 원리대로 구현하면 됨

2차원 배열인 dist[][] 만들고 초기화한 후 정점 1부터 갱신하는 것을 N번 반복

벨만 포드 알고리즘

• 한 정점에서 다른 모든 정점으로 가는 데에 걸리는 최단 경로 찾음
• 모든 경우의 수를 탐색하면서 최단 경로를 찾음 (그리디 X)
• 음의 간선이 있어도 가능 (음의 사이클 찾아내기 가능)
• 다익스트라 알고리즘을 사용하지 못할 경우 사용하기
• 시간 복잡도 O(VE) (V: 정점, E: 간선)

동작 원리

dist[]에 비용 저장, INF로 초기화

맨 처음 노드의 dist[]는 0

1. 모든 간선들을 탐색하면서 간선을 잇는 출발 노드가 한번이라도 계산된 적 있다면 갱신 (해당 간선이 잇는 정점의 거리 비교해서 업데이트)
2. 1의 과정을 N-1번 반복
3. 마지막에 1번 더 탐색했을 때 갱신되는 dist가 있다면 음의 사이클이 발생한 것

구현 방법

• 간선의 정보 저장한 Edge vector ( start, end, cost ), INF로 초기화 되어 있는 dist[] 만들기
• dist[1] 을 0으로 만들어줌 (맨 처음)
• N-1번 간선을 탐색하기(E번 만큼)
• N번째 탐색에서 갱신이 이뤄진다면 음의 사이클 존재한다는 것