그래프 - 벨만-포드 알고리즘

#include <iostream>
#include <vector>
#define INF 1 << 30
using namespace std;
typedef long long ll;
    
vector<vector<pair<ll, ll>>> adj;     //정점 "u" -> 정점 "adj[u][i].first"의 비용 = adj[u][i].second
ll table[501];     //table[i]는 모두 INF로 초기화되어 있어야 한다.

 

//함수가 false를 리턴하면 "start->임의의 정점" 사이에 cost가 무한히 감소하는 사이클이 있다는 뜻이다.

//만일 볼드체로 표시한 line을 삭제하면 "start->임의"가 아닌 "임의->임의" 사이에 무한히 감소하는 사이클이 있어도 false를 리턴한다.

bool bellman_ford(int start, int v_num) {        //v_num은 정점의 개수. 
    bool renew = false;
    table[start] = 0;
    for (int i = 0; i < v_num; i++) {        //정점 개수 만큼 갱신한다.
        renew = false;
        for (int u = 1; u <= v_num; u++) {
            if (table[u] == INF) continue;        //아직 정점 u가 한번도 start와 연결되지 않았으면 넘어감
            for (int v = 0; v < adj[u].size(); v++) {      //u와 연결된 정점들에 대하여 테이블 갱신
                ll newVert = adj[u][v].first;
                ll newCost = table[u] + adj[u][v].second;
                if (table[newVert] > newCost) {
                    table[newVert] = newCost;
                    renew = true;
                }
            }
        }
        if (!renew) break;      //값의 갱신이 한번도 일어나지 않음(==더이상 변화가 없을 예정임)
    }
    if (renew) return false;        //마지막까지도 비용이 갱신되었다면 사이클이 있다는 뜻임.
    return true;
}