[최단거리 알고리즘] 다익스트라(Dijkstra), 플로이드와샬(FloydWarshall)

1. 다익스트라 알고리즘

한 정점에서 모든 정점으로의 최단경로를 구하는 알고리즘이다.

https://www.acmicpc.net/problem/1753

1753번: 최단경로

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#define INF 1000000000
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int v, e, start; // 정점의 수, 간선의 수, 시작 정점 번호 (정점은 1번부터)
    cin >> v >> e;
    cin >> start;

    //vector<pair<int, int> > vp[v + 1];
    vector<vector<pair<int, int> > > vp(v + 1, vector<pair<int, int> >());

    int a, b, c;
    for (int i = 0; i < e; i++)
    {
        cin >> a >> b >> c; // a -> b로 가는 간선의 비용이 c
        vp[a].push_back(make_pair(c, b));
    }

    // 최단거리 배열 초기화
    vector<int> d(v + 1, INF);
    d[start] = 0;

    // 우선순위 큐 초기화
    priority_queue<pair<int, int> > pp;
    pp.push(make_pair(0, start));

    int cur_distance, next_distance;
    int cur_vertex, next_vertex;
    while (!pp.empty())
    {
        cur_distance = -pp.top().first;
        cur_vertex = pp.top().second;
        pp.pop();

        if (d[cur_vertex] < cur_distance)
            continue;

        for (int i = 0; i < vp[cur_vertex].size(); i++)
        {
            next_distance = vp[cur_vertex][i].first;
            next_vertex = vp[cur_vertex][i].second;

            if (cur_distance + next_distance < d[next_vertex])
            {
                d[next_vertex] = cur_distance + next_distance;
                pp.push(make_pair(-(cur_distance + next_distance), next_vertex));
            }
        }
    }

    for (int i = 1; i < d.size(); i++)
    {
        if (d[i] == INF)
            cout << "INF"
                 << "\n";
        else
            cout << d[i] << "\n";
    }
}

 

2. 플로이드 와샬 알고리즘

모든 정점에서 모든 정점으로의 최단경로를 구하는 알고리즘이다.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > floydWarshall(vector<vector<int> > &v) {
    int n = v.size();
    vector<vector<int> > d(n, vector<int>(n, 0));

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            d[i][j] = v[i][j];
        }
    }

    // k = 거쳐 가는 노드
    for (int k = 0; k < n; k++) {
        // i = 출발 노드
        for (int i = 0; i < n; i++) {
            // j = 도착 노드
            for (int j = 0; j < n; j++) {
                if (d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
            }
        }
    }

    return d;
}

void printSolution(vector<vector<int> > &v){
    int n = v.size();
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++) {
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}


int main() {
    const int INF = 1000000000;
    vector<vector<int> > v1{
        {0,   2,   5, 1,   INF, INF},
        {2,   0,   3, 2,   INF, INF},
        {5,   3,   0, 3,   1,   5},
        {1,   2,   3, 0,   1,   INF},
        {INF, INF, 1, 1,   0,   2},
        {INF, INF, 5, INF, 2,   0}
    };

    vector<vector<int> > v2{
        {0,   5,  INF, 10},
        {INF,  0,  3,  INF},
        {INF, INF, 0,   1},
        {INF, INF, INF, 0}
    };

    vector<vector<int> > answer = floydWarshall(v1);
    printSolution(answer);

    answer = floydWarshall(v2);
    printSolution(answer);

    return 0;
}