SHARE
TWEET

Bellman-Ford algorithm

keverman Jan 12th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Detects negative cycles in a weighted graph
  2. bool Bellman_Ford(int src)
  3. {
  4.     std::vector<int> distance(size(), 0x3f3f3f3f);
  5.     distance[src] = 0;
  6.  
  7.     for(int i = 0; i < size(); i++)
  8.         for(int from = 0; from < size(); from++)
  9.             if(distance[from] != 0x3f3f3f3f)
  10.                 for(edge &e : edges[from])
  11.                     distance[e.to] = std::min(distance[e.to], e.weight + distance[from]);
  12.  
  13.     for(int from = 0; from < size(); from++)
  14.         if(distance[from] != 0x3f3f3f3f)
  15.             for(edge &e : edges[from])
  16.                 if(distance[from] + e.weight < distance[e.to])
  17.                     return true;
  18.  
  19.     return false;
  20. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top