Bellman ford's shortest path algorithm for finding shortest path

bellman_ford.cc

#include <vector>
#include <queue>
#include <iostream>
#include <stdexcept>

using namespace std;

// bellman ford's algorithm is an algorithm that finds shortest path
// unlike dijkstra's algorithm, it also works while the cost is negative.
// the time complexity is O(V·E)

// it works as follows, 
// iterate through every node, and examine their outward edges, 
// if the cost + cost[begin] is less than the curr cost of the vertex
// then update that vertex. Finally we iterate at most NUM_OF_VERTICES - 1 times.

// Here is a great explaination video.
// https://www.youtube.com/watch?v=obWXjtg0L64&vl=en
vector<int> bellmanford(vector<vector<pair<int, int>>>& graph) {
  vector<int> dp(graph.size(), INT_MAX);
  dp[0] = 0;
  for (int i = 0; i < graph.size() - 1; i++) {
    for (int curr = 0; curr < graph.size(); curr++) {
      if (dp[curr] == INT_MAX) continue;
      for (auto pair : graph[curr]) {
        const int dest = pair.first;
        const int cost = pair.second;
        dp[dest] = min(dp[dest], cost + dp[curr]);
      }
    }
  }
  return dp;
}

// optimized version with shortest route recording
// since the outer for loop needs at most VERTICES - 1 times, 
// if one iteration through every vertex doesn't update anything
// we don't have to iterate VERTICES - 1 times, but end up earlier.
pair<vector<int>, vector<int>> bellmanford_opt(vector<vector<pair<int, int>>>& graph) {
  vector<int> dp(graph.size(), INT_MAX);
  vector<int> predecessor(graph.size(), -1);
  dp[0] = 0;
  for (int i = 0; i < graph.size(); i++) {
    bool hasChanged = false;
    for (int curr = 0; curr < graph.size(); curr++) {
      if (dp[curr] == INT_MAX) continue;
      for (auto pair : graph[curr]) {
        const int dest = pair.first;
        const int cost = pair.second;
        const int newCost = cost + dp[curr];
        if (newCost < dp[dest]) {
          // since NUM_OF_VERTICES - 1 loops guarantees the shortest path,
          // if we run one more times and the dp table still updatable, 
          // a negative cycle is detected.
          if (i == graph.size() - 1) throw logic_error("Negative cycle detected.");
          dp[dest] = newCost;
          predecessor[dest] = curr;
          hasChanged = true;
        }
      }
    }
    if (!hasChanged) break;
  }
  return { dp, predecessor };
}

int main() {
  // s: 0, a: 1, b: 2, c: 3, d: 4, e: 5
  // pair.first => destination
  // pair.second => cost
  vector<vector<pair<int, int>>> graph{
    { {1, 10}, {5, 8} },
    { {3, 2} },
    { {1, 1} },
    { {2, -2} },
    { {3, -1}, {1, -4} },
    { {4, 1} }
  };
  // un-comment this to try the negative cycle detection
//   vector<vector<pair<int, int>>> neg_graph{
//     { {1, 5}, {2, 4} },
//     { {3, 3} },
//     { {1, -6} },
//     { {2, 2} }
//   };
  auto ans = bellmanford_opt(graph);
  cout << "cost = ";
  for (auto i : ans.first)
    cout << i << " ";
  cout << endl;
  
  int dest = 3;
  deque<int> path;
  while (dest != -1) {
    path.push_front(dest);
    dest = ans.second[dest];
  }
  cout << "path = ";
  for (auto i : path)
    cout << i << " ";
  cout << endl;
}

Normal graph used in the code.

Negative cycle graph in the code, this is actually taken from here.