다익스트라, 벨만포드 알고리즘

다익스트라 알고리즘

언제 사용?

하나의 시작 노드로부터 모든 다른 노드까지의 최단경로를 찾는 알고리즘이다.(벨만포드와 같다)
가중치가 0이거나 양수인 경우만 사용할 수 있다.
가중치가 음수라면 사용할 수 없다.

구현 방법

사용 변수
vertex 개수 , edge 개수, start_node 값,
사용 자료구조
최소거리를 담은 배열, 방문했는지 기록하는 배열, 이전 노드를 기록하는 배열(방문순서를 기록하기 위함) 인접리스트,

우선순위 큐

어떻게 작동?

우선순위 큐에 시작 노드를 넣는다.
아래를 반복한다.
우선순위 큐가 비면 반복을 멈춘다.
우선순위 큐에서 노드를 꺼낸다.
방문한 노드면 즉시 continue한다.
방문하지 않는 노드면 방문 표시를 하고, 인접노드를 전부 순회한다.
매 순회마다 이를 반복한다.
더 좋은 최단 경로를 찾았다면 인접노드에 대한 최소거리를 update하고, 우선순위 큐에 넣는다.
(지금까지 구한 최소거리 > 현재 구한 최소거리)

왜 음수일때 사용 불가능?

왜냐하면 다익스트라는 그리디 하기 때문이다.
음수 가중치가 있는 상황에서는 그리디 방법으로 최단 경로를 구할 수 없다.
노드1에서 노드2로 가는데 2분이 걸리고 노드2에서 노드3으로 가는데 -5분이 걸린다고 하자.
노드1에서 노드3으로 1분이 걸린다고 하자.
이 상황에서 다익스트라는 노드1에서 노드3번으로 가는게 최단이라고 확정짓는다.
가장 가까운 노드부터 방문하고,
이미 기록된 최단경로는 다시 바뀌지 않을 것이라고 믿기 때문이다.

시간 복잡도

다익스트라의 총 시간 복잡도는 O((V+E)log⁡V)로 표현된다.
O(Vlog⁡V) : 정점(V)의 최단 경로를 큐에서 꺼내는 작업.
O(ElogV): 간선(E)을 따라 최단 경로를 갱신하는 작업(각 간선에 대해 최단 경로 갱신 여부를 확인하는 작업)
최단 경로가 결정되는 과정에서, 각 간선은 최대 한 번만 유효하게 처리되기 때문에 O(E)라는 복잡도가 성립

각 노드를 반복할때마다 인접노드를 순회하는데 그러면 V^2아닌가?
=>결국 간선의 총 개수 미만으로 순회를 할 것이므로 총 작업량은 최대 O(E)이다.

코드

#include <bits/stdc++.h>  
using namespace std;  
int v, e, s;  
vector<int> MD;  
struct Edge {  
    int next_node, w;  
    Edge(int next_node, int w) : next_node(next_node), w(w) {};  
    bool operator<(const Edge& other) const {  
        return w > other.w;  
    }  
};  
vector<vector<Edge>> adj_list;  
priority_queue<Edge> pq;  
vector<int> visite_d;  
vector<int> previous_node;  
void algo() {  
    MD[s] = 0;  
    pq.emplace(s, 0);//넣을때 visited true안하고 꺼낼 때 해서 안함.  
    while (!pq.empty()) {  
        Edge current = pq.top(); pq.pop();  
        if (visite_d[current.next_node]) continue;  
        int current_node = current.next_node;  
        visite_d[current_node] = true;  
        for (auto& [next_node, w] : adj_list[current_node])  
            if (MD[next_node] > MD[current_node] + w)  
                MD[next_node] = MD[current_node] + w,  
                previous_node[next_node] = current_node,  
                pq.emplace(next_node,MD[next_node]);  
    }  
}  
int main() {  
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
    cin >> v >> e >> s;  
    MD.resize(v + 1, INT_MAX);  
    adj_list.resize(v + 1, vector<Edge>());  
    visite_d.resize(v + 1, false);  
    previous_node.resize(v + 1, -1);  
    for (int imm = 0; imm < e; imm++) {  
        int start, end, w;  
        cin >> start >> end >> w;  
        adj_list[start].emplace_back(end, w);  
    }  
    algo();  
    for (int i = 1; i <= v; i++)  
        if (visite_d[i]) cout << MD[i] << "\n";  
        else cout << "INF\n";  
}

벨만포드 알고리즘

언제 사용?

하나의 시작 노드로부터 모든 다른 노드까지의 최단경로를 찾는 알고리즘이다.(벨만포드와 같다)
가중치에 음수가 있는 경우에도 사용할 수 있다.
그래프에 음수 사이클이 있는지 없는지도 파악할 수 있다.

구현 방법

어떻게 작동?

다음을 V-1번 반복한다.
간선 리스트의 요소를 전부 순회한다.
그 때마다 더 좋은 최단경로를 찾았다면 갱신한다.

음수사이클이 있는지 없는지 파악하고 싶으면 V-1번을 반복을 한 다음에,
1번을 더 반복했을 때 최단경로가 또 찾아지는지 아닌지 확인하면 된다.
음수 사이클이 없다면 V-1번 반복으로 최단경로는 확정된다.
음수 사이클이 있다면 V-1번 반복 이후에도 무한정으로 최단경로가 찾아진다.

왜? 단순히 똑같은 반복을 V-1번하는 데 최단경로가 구해지는 걸까?
간선리스트의 데이터에 start,end,w가 있다.
벨만포드 알고리즘은
간선리스트를 전부 확인해서
end의 최소거리를 업데이트 한다.
이 행위를 relax라고 부르자.
그러면 relax를 1번만 수행한다면, 2 홉 이상으로 결정되는 모든 경로를 고려하지 못한다.
한번의 relax로도 2홉의 경로가 어느정도는 고려가 된다. 하지만 2번의 relax를 해야 2홉의 경로가 모두 고려가 된다.

구현 코드

#include <iostream>  
#include <vector>  
#include <limits.h>  
#include <tuple>  
using namespace std;  
vector<long> MD;  
int v, e, s;  
struct Edge {  
    int start, end, w;  
    Edge(int start, int end, int w) : start(start), end(end), w(w) {}  
};  
vector<Edge> edge_list;  
bool cycle = false;  
void algo() {  
    MD[s] = 0;// 아래처럼 단일 문장으로 가능해  
    for (int imm = 1; imm <= v - 1; imm++)  
        for (auto& [start, end, w] : edge_list)  
            if (MD[start] != LONG_MAX &&  
                MD[end] > MD[start] + w)  
                MD[end] = MD[start] + w;  
}  
void find_cycle() { // 얘도 단일 문장으로 가능해.  
    for (auto& [start, end, w] : edge_list)  
        if (MD[start] != LONG_MAX &&  
            MD[end] > MD[start] + w)  
            cycle = true;  
}  
int main()  
{  
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
    cin >> v >> e; s = 1;  
    MD.resize(v + 1, LONG_MAX);  
    for (int i = 0; i < e; i++) {  
        int start, end, w;  
        cin >> start >> end >> w;  
        edge_list.emplace_back(start, end, w);  
    }  
    algo();  
    find_cycle();  
    if (!cycle)  
        for (int i = 2; i <= v; i++)  
            if (MD[i] == LONG_MAX)  
                cout << -1 << "\n";  
            else  
                cout << MD[i] << "\n";  
    else  
        cout << -1 << "\n";  
    return 0;  
}