다익스트라, 플로이드

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의

 

https://blog.naver.com/jhc9639/222349335717

[알고리즘 강의] 8주차. 펜윅트리와 최단거리알고리즘(다익스트라, 플로이드워셜, 벨만포드)

 수업을 듣고 정리한 글입니다.

 

다익스트라

한 정점에서 다른 모든 정점까지 최단거리를 구하는 알고리즘

우선순위 큐 + bfs를 사용한다.

 

다익스트라 구현 코드

#include <bits/stdc++.h>
using namespace std;

int a,b,n,u,w,v;
vector<pair<int,int>> adj[20004];
int dist[20004];
const int INF = 987654321;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> a >> b; //정점의 개수, 간선의 개수
    cin >> n; //시작 정점의 번호
    fill(dist, dist+20004,INF); //거리 INF로
    for(int i=0;i<b;i++){
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w,v)); //u->v, 가중치 w, 인접정점
    }
    //2. 우선순위 큐 수행
    pq.push({0,n}); //가중치 0, 시작위치
    dist[n]=0; //시작정점의 거리는 0
    while(pq.size()){
        int here = pq.top().second; //위치
        int here_dist = pq.top().first; //거리
        pq.pop();
        if(dist[here] != here_dist) continue; //거리가 다르다=방문했다.
        //인접한 점에 대해
        for(pair<int,int> there:adj[here]){
            int _dist = there.first;
            int _there = there.second;
            //거리 작은 걸로 업데이트
            if(dist[_there]>dist[here]+_dist){
                dist[_there]=dist[here]+_dist;
                pq.push({dist[_there], _there});
            }
        }
    }
    //2. 출력
    for(int i=1;i<=a;i++){
        if(dist[i]==INF) cout << "INF\n";
        else cout << dist[i]<<"\n";
    }
    return 0;
}

 

플로이드 워셜

모든 정점에서 다른 모든 정점까지 최단거리를 구하는 알고리즘

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

경유점을 거쳐서 가는것이 더 빠른지 생각한다. 

 

반복문 시에 k, i, j 순서 기억하기!

 

11404번: 플로이드 https://www.acmicpc.net/problem/11404

11404번: 플로이드

문제: 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성

모든 도시에 대한 비용 최솟값 구하기 => 플로이드 워셜

 

플로이드 코드

#include <bits/stdc++.h>
using namespace std;

int n,m, dist[104][104],a,b,c;
const int INF = 987654321;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n >> m;
    fill(&dist[0][0], &dist[0][0]+104*104,INF);
    for(int i=0;i<m;i++){
        cin >> a >> b >> c;
        a--;b--;
        dist[a][b]=(dist[a][b]?min(dist[a][b],c):c);
    }
    //2. 플로이드 수행
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }
    //3. 출력
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j) cout << "0 ";
            else cout << (dist[i][j]==INF?0:dist[i][j]) << " ";
        }
        cout << "\n";
    }
}