최단경로 알고리즘

1. 플로이드 워셜

* 이론
모든 지점에서 다른 지점까지의 최단거리를 계산할 때 쓰임.
시작지점을 잡고 목표지점을 잡는다
시작에서 목표로 가는데 이 사이에 어떠한 중간지점을 껴서 가는 게 더 짧다면 이 짧은 거리로 경로를 갱신
이거를 모든 곳에서 함
(모든 시작 모든 목표 모든 중간에서 함)

비어있는 곳은 엄청큰수(inf)로 설정 후 진행

 

* 구현
for문 세 개 쓰면 됨(중간 - 시작 - 끝 순서로)

만약 그래프의 특정 경로가 중간 지점 거친 경로보다 더한 게 더 크면 갱신

for (int k=0; k<N; k++) { // 거쳐가는 노드(중간 노드)
    for (int i=0; i<N; i++) { // 시작 노드
        for (int j=0; j<N; j++) { // 끝 노드
            if (graph[i][j] > graph[i][k] + graph[k][j]) {
                graph[i][j] = graph[i][k] + graph[k][j]; // 갱신
            }
        }
    }
}

 

* 시간 복잡도

-> n의 3승 시간복잡도 가짐(n은 노드의 개수)

=> 노드 개수 많으면 쓸 수 없음

2. 다익스트라

* 이론
1개의 노드에서 다른 모든 노드로 가는 최단거리

하나의 최단거리를 구할 때 이전까지 구했던 최단 거리 정보를 이용한다.

현재까지 알고 있던 최단 경로를 계속 갱신함

 

* 다익스트라랑 bfs 비교
bfs : 큐 사용해서 방문배열 사용
다익스트라 : 우선순위큐 사용해서 최단거리배열 사용
=> bfs랑 비슷하게 구현가능

가장 짧은 거리 가진 애 갖고 와서(우선순위큐가 해줌) 다른 노드로 탐색 진행

 

* 구현

1. 출발 노드 설정

2. 출발 노드 기준으로 각 노드의 최소 비용 저장

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택

4. 해당 노드 거쳐서 특정 노드로 가는 경우를 고려해서 최소 비용 갱신

5. 3,4번 반복

 

우선순위 큐와 인접 리스트 방식으로 구현

vector<pair<int,int>> a[N]; // 각 노드들의 연결 정보를 담은 벡터
int d[N]; // 최단 거리를 담은 배열
// N은 정점의 개수

void dijkstra(int start) {
    d[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int cur = pq.top().second;
        int dis = pq.top().first;
        pq.pop();

        if (d[cur] < dis) continue;
        for (int i = 0; i < a[cur].size(); i++) {
            int next = a[cur][i].first;
            int nextDis = dis + a[cur][i].second;

            if (nextDis < d[next]) {
                d[next] = nextDis;
                pq.push({nextDis, next});
            }
        }
    }
}

 

다이나믹 프로그래밍 적용하여 구현

 

 

* 시간 복잡도

- 인접 리스트 방식

n
heap(tree 자료구조) 정렬시 logn
=> n log n

 

- 다이나믹 프로그래밍 적용시

선형 탐색으로 찾으므로 n^2

 

참고 : https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘