반응형
개념
다익스트라(dijkstra)알고리즘은 다이나믹 프로그래밍(dp)를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
23. 다익스트라(Dijkstra) 알고리즘
다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest P...
blog.naver.com
2차원 배열로 간선의 정보를 저장한다. 서로 연결되어 있지 않은 경우는 무한의 수로 설정한다.
- 음의 간선 정보는 포함 할 수 없다.
- 방문하지 않은 노드중 가장 비용이 적은 노드를 선택
구현 방법
- 간선 정보 2차원 배열로 생성, 최단 거리 배열 생성
#define INF 1e9 //엄청 큰 값인 10억
vector<pair<int,int>> v[10001]; // 비용, 연결점
int d[10001];
fill(d, d+10001, INF);
최단 거리 배열은 가장 작은 값을 나타내야 하기 때문에 우선은 가장 큰 값으로 초기화해 놓는다.
- priority_queue를 이용하여 최소비용 순서로 다익스트라 알고리즘 적용
void dijkstra(int start) {
priority_queue<pair<int,int>> pq;
pq.push({0,start});
d[start] = 0;
while(!pq.empty()) {
int dist = -pq.top().fist; // 현재 노드까지의 비용, 작은것부터 뽑기위해 -로 저장해놨음
int now = pq.top().second; // 현재 노드
pq.pop();
if(d[now] < dist) continue; // 현재 노드까지의 비용이 더 크면 볼 것도 없음
for(int i = 0; i < v[now].size(); i++) {
int cost = dist + v[now][i].first; //현재노드까지의 비용 + 다음 노드로 가는 비용
if(cost < d[v[now][i].second]) {
d[v[now][i].second] = cost
pq.push(make_pair(-cost, v[now][i].second));
}
}
}
}
현재까지의 비용이 가장 적은 노드 선택 후 그 노드와 연결된 노드들의 비용 값을 구한 후 만약 구한 값이 원래의 값보다 더 작다면 값을 업데이트 해 준 후 우선순위 큐에 해당 노드를 넣는다.
전체 코드
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
vector<pair<int, int> > graph[100001]; // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
int d[100001]; // 최단 거리 테이블 만들기
void dijkstra(int start)
{
priority_queue<pair<int,int>>pq; // 거리, 노드 인덱스
pq.push({0,start}); //시작 노드로 가기위한 최단 경로는 0으로 설정하여, 큐에 삽입.
d[start]=0;
while(!pq.empty())
{
int dist = -pq.top().first; //현재 노드까지의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
if(d[now]<dist) // 이미 최단경로를 체크한 노드인 경우 패스
continue;
for(int i=0; i<graph[now].size(); i++)
{
int cost = dist+graph[now][i].second; // 거쳐서 가는 노드의 비용을 계산
// 현재노드까지 비용 + 다음 노드 비용
if(cost<d[graph[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
{
d[graph[now][i].first]=cost;
pq.push(make_pair(-cost,graph[now][i].first));
}
}
}
}
int main(void)
{
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({b, c});
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill(d, d + 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++)
{
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\\n';
}
}
}
시간 복잡도
O(N * logN)
반응형
'코딩 낙서' 카테고리의 다른 글
| 카카오기출 - 순위 검색 (0) | 2023.06.23 |
|---|---|
| 알고리즘 - 인덱스 트리(Index Tree) (0) | 2023.06.21 |
| 알고리즘 - 크루스칼(Kruskal) (0) | 2023.06.21 |
| 알고리즘 - 누적합(Prefix Sum) (0) | 2023.06.21 |
| 알고리즘 - Union & Find (0) | 2023.06.21 |
