문제

문제 링크 : https://www.acmicpc.net/problem/11404 (단계별로 풀어보기 : 최단 거리)

문제 풀이

해당 문제는 플로이드 와샬 알고리즘 문제이다. 일단 플로이드 와샬 알고리즘이란 모든 정점에서 다른 정점으로의 최단거리를 구할 때 사용하고 음수의 간선이 있어도 상관없다. 대신 시간복잡도가 O(n^3) 으로 정점의 개수가 작을 때만 가능하다. 알고리즘 구현은 동적계획법으로 생각하는게 이해하기 쉽다. 처음 최단거리 테이블을 이차원으로 만들고 INF값으로 초기화해준다. 그리고 자기 자신으로 가는 경우 즉 table[i][i] = 0 으로 초기화 한다. 그 다음 k를 1~n 까지 반복하면서 k가 중간 지점으로 생각하고 테이블을 갱신한다.

점화식은 다음과 같다.
table[i][j] = min(table[i][j], table[i][k] + table[k][j])

이 점화식을 이용하면 구현하기는 어렵지 않다.
또한 이문제는 dijkstra 알고리즘을 n번 반복해도 풀리는 문제이다. 우선순위 큐로 구현할시 시간복잡도가 O(ElogE)인데 n번 반복하기 때문에 O(nElogE)라 생각하였는데 직접 구현하여 제출해봤더니 생각과 달랐다. 여러분도 한번 생각해 보면 좋을 것 같다.
해당 링크를 한번 보면 이해하기 좋을 것 같다.

알고리즘 스케치

소스코드

Floyd Warshall

#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define INF 1e10
#define ll long long
using namespace std;

vector <vector<ll>> table;
int n, m;

void input();
void FloydWarshall();

int main()
{
    fastio;
    input();
    FloydWarshall();
    return 0;
}

void input()
{
    cin >> n;
    cin >> m;
    table.resize(n+1);
    for(int i=1; i<n+1; i++){
        table[i].resize(n+1);
        fill(table[i].begin(),table[i].end(),INF);
    }
    for(int i=1, j=1; i<=n; i++,j++) table[i][j]=0;
    int a,b,c;
    for(int i=0; i<m; i++){
        cin >> a >> b >> c;
        if(table[a][b]>c)   table[a][b] = c;
    }
}

void FloydWarshall()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                table[i][j] = min(table[i][j], table[i][k]+table[k][j]);

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(table[i][j]!=INF)
                cout << table[i][j] << " "; 
            else
                cout << 0 << " ";
        }
        cout << "\n";
    }
}

Dijkstra

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define INF 1e9
#define ll long long
using namespace std;

typedef struct{
    int v,c;
}node;
vector <vector<node>> graph;
vector <vector<ll>> table;
priority_queue <pair<int,int>> que;
int n, m;

bool compare(node a, node b)
{
    if(a.v!=b.v)
        return a.v < b.v;
    else
        return a.c < b.c;   
}
void input();
void dijkstra(int start);

int main()
{
    fastio;
    input();
    for(int i=1; i<n+1; i++) dijkstra(i);
    return 0;
}

void input()
{
    cin >> n;
    cin >> m;
    graph.resize(n+1);
    int a;
    node tmp;
    for(int i=0; i<m; i++){
        cin >> a >> tmp.v >> tmp.c;
        graph[a].push_back(tmp);
    }
    for(int i=1; i<n+1; i++) sort(graph[i].begin(),graph[i].end(),compare);
}

void dijkstra(int start)
{
    int check[n+1];
    for(int i=1; i<n+1; i++) check[i] = INF;
    check[start] = 0;
    que.push(make_pair(0,start));
    int curnode, cost, nodesize, v, pre_v=0;
    while(que.size()!=0){
        cost = -que.top().first;
        curnode = que.top().second;
        que.pop();
        nodesize = graph[curnode].size();
        for(int i=0; i<nodesize; i++){
            v = graph[curnode][i].v;
            if(v==pre_v) continue;
            if(cost + graph[curnode][i].c < check[v]){
                check[v] = cost + graph[curnode][i].c;
                que.push(make_pair(-check[v],v));
            }
            pre_v = v;
        }
    }
    for(int i=1; i<=n; i++){
        if(check[i]!=INF)
            cout << check[i] << " ";
        else
            cout << 0 << " ";
    }
    cout << "\n";
}