Dijkstra, Bellman-Ford, Floyd-Warshall

 

다익스트라

shnoh.tistory.com/15

예제

codingfarm.tistory.com/300

codingfarm.tistory.com/301

BFS와 유사한 형태지만, BFS는 이미 지나간 노드는 새로운 진입을 철저히 막는 반면

다익스트라는 새로 들어온 진입으로의 경로가 기존의 값보다 더 낫다면 새로운 진입이 가능해진다.

#include<iostream>
#include<vector>
 
#define INF 2000000000
 
using namespace std;
 
vector<vector<int>> bridges;    // bridges[i] : i번 노드에서 이동가능한 노드 목록
vector<vector<int>> weights;
vector<int> distances, predecessor;
 
int main(void) {
    int n, k;
    cin >> n >> k;
    bridges.assign(n, vector<int>(0, INF));
    weights.assign(n, vector<int>(0, INF));
    distances.assign(n, INF);
    predecessor.assign(n, INF);
    int from, to, weight;
    for (int i = 0; i < k; i++) {
        cin >> from >> to >> weight;
        from--, to--;
        bridges[from].push_back(to);
        weights[from].push_back(weight);
    }
 
    distances[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int node = 0; node < n; node++) {
            for (int j = 0; j < bridges[node].size(); j++) {
                int next = bridges[node][j];
                int weight = weights[node][j];
 
                if (distances[node] != INF && distances[next] > distances[node] + weight) {
                    distances[next] = distances[node] + weight;
                    predecessor[next] = node;
                }
            }
        }
    }
 
 
    return 0;
}
 
 
/*
5 9
1 2 3
1 3 8
1 5 -4
2 4 1
2 5 7
3 2 4
4 1 2
4 3 -5
5 4 6
 
*/

 

 

 

벨만포드

ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/

 

벨만포드는 음의 사이클이 존재하면 사용할 수 없는 알고리즘인데, 이를 역으로 활용하여 음의 사이클의 존재 여부를 확인할 수 있다.

 

 

 

플로이드 워셜

hsp1116.tistory.com/45

#include<iostream>
#include<vector>
#include<stack>
#include<string>
 
#define INF 2000000000
 
using namespace std;
 
// inbounds[a][b] : a에서 b 노드로 최단경로로 이동할때 b노드로 들어오게 되는 노드 번호
vector<vector<int>> inbounds;
 
// dis[a][b] : a에서 b로 가기위한 최저가중치
vector<vector<int>> dist;
 
 
void FloydWarshall() {
    int N = inbounds.size();
    for (int term = 0; term < N; term++) {
        for (int to = 0; to < N; to++) {
            for (int from = 0; from < N; from++) {
                if (dist[from][term] != INF && dist[term][to] != INF) {
                    if (dist[from][to] > dist[from][term] + dist[term][to]) {
                        dist[from][to] = dist[from][term] + dist[term][to];
                        inbounds[from][to] = inbounds[term][to];
                    }
                }
            }
        }
    }
}
 
 
void PringBoard(string title, vector<vector<int>>& board) {
    cout << title << endl;
    for (int row = 0; row < board.size(); row++) {
        for (int col = 0; col < board[0].size(); col++) {
            cout << board[row][col] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
 
 
stack<int> GetPath(int from, int to) {
    int term;
    stack<int> st;
 
    if (from == to) {
        cout << endl;
        return st;
    }
 
    st.push(to);
    while (1) {
        to = inbounds[from][to];
        st.push(to);
        if (from == to)
            break;
    }
 
    while (!st.empty()) {
        cout << st.top() << " - ";
        st.pop();
    }
    cout << endl;
 
    return st;
}
 
int main(void) {
    int n;
    cin >> n;
 
    inbounds.assign(n, vector<int>(n, INF));
    dist.assign(n, vector<int>(n, INF));
 
    for (int i = 0; i < n; i++) {
        inbounds[i][i] = INF;
        dist[i][i] = 0;
    }
 
    int k;
    cin >> k;
    int from, to, weight;
    for (int i = 0; i < k; i++) {
        cin >> from >> to >> weight;
        from--, to--;
        // inbounds[from][to] = from;
        //dist[from][to] = weight;
        if (dist[from][to] > weight) {
            dist[from][to] = weight;
            inbounds[from][to] = from;
        }
    }
    PringBoard("dist", dist);
    PringBoard("inounds", inbounds);
 
    FloydWarshall();
 
    PringBoard("dist", dist);
    PringBoard("inounds", inbounds);
 
    for(int from = 0; from < n; from++)
        for (int to = 0; to < n; to++) {
            cout << from << "에서 " << to << "까지의 경로 : ";
            GetPath(from, to);
        }
 
    return 0;
}
 
 
/*
5 9
1 2 3
1 3 8
1 5 -4
2 4 1
2 5 7
3 2 4
4 1 2
4 3 -5
5 4 6
 
*/