벨만포드 알고리즘

다익스트라 알고리즘과 함께 또 다른 최단거리를 구하는 알고리즘으로 '벨만포드 알고리즘'이 존재한다.

둘의 가장 큰 차이점은 '음수 간선을 포함할 때 최단거리를 구할 수 있는 지' 이다. 다익스트라 알고리즘은 음수 간선을 포함한 그래프라면 최단거리를 찾을 수 없고, 벨만포드 알고리즘은 찾을 수 있다.
또한 둘은 알고리즘의 진행 방식에서도 차이가 존재한다. 다익스트라 알고리즘은 greedy 알고리즘을 활용해 현재노드의 주변 노드에서 최단거리 값을 가진 노드를 선택한다면, 벨만포드 알고리즘은 generic 알고리즘과 greedy알고리즘을 함께 활용하여 매 단계마다 모든 간선을 확인하면서 모든 노드간의 최단거리에서 선택을 한다.

벨만포드 알고리즘의 핵심은 'negative cycle'의 존재 유무 이다. negative cycle이 존재할 경우 최단거리는 매번 갱신이 되면서 최적해를 찾을 수 없게 된다. 따라서 negative cycle이 존재하는 지 검사를 하여 없을 경우에만 최단거리를 선택해야 한다.

->negative cycle 포함된 그래프

알고리즘의 단계는 아래와 같다.

1. 출발노드를 설정한다.
2. 최단거리 테이블을 초기화한다. (출발노드는 0으로 초기화)
3. 간선 선택 (반복구간 - greedy 알고리즘 사용)
   - 모든 간선 확인 (negative cycle 존재 확인)
   if d[v] > w[u,v]:
   d[u]<-d[u]+wu,v

관련 문제: leetcode 743
다익스트라 알고리즘 코드:

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        int res = 0;
        vector<vector<int>> edges(101, vector<int>(101, -1));
        queue<int> q{{K}};
        vector<int> dist(N + 1, INT_MAX);
        dist[K] = 0;
        for (auto e : times) edges[e[0]][e[1]] = e[2];
        while (!q.empty()) {
            unordered_set<int> visited;
            for (int i = q.size(); i > 0; --i) {
                int u = q.front(); q.pop();
                for (int v = 1; v <= 100; ++v) {
                    if (edges[u][v] != -1 && dist[u] + edges[u][v] < dist[v]) {
                        if (!visited.count(v)) {
                            visited.insert(v);
                            q.push(v);
                        }
                        dist[v] = dist[u] + edges[u][v];
                    }
                }
            }
        }
        for (int i = 1; i <= N; ++i) {
            res = max(res, dist[i]);
        }
        return res == INT_MAX ? -1 : res;
    }
};
  

벨만포드 알고리즘:

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        int res = 0;
        vector<int> dist(N + 1, INT_MAX);
        dist[K] = 0;
        for (int i = 1; i < N; ++i) {
            for (auto e : times) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {		// negative cycle 검사
                    dist[v] = dist[u] + w;
                }
            }
        }
        for (int i = 1; i <= N; ++i) {
            res = max(res, dist[i]);
        }
        return res == INT_MAX ? -1 : res;
    }
};

참고: https://www.cnblogs.com/grandyang/p/8278115.html