Guest User

Untitled

a guest
May 20th, 2013
36
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. int edmondsKarp(int startNode, int endNode)
  2. {
  3. int maxFlow=0;
  4.  
  5. while(true)
  6. {
  7.     // we find an augmented path and the maximum flow corresponding to it
  8.     int flow=bfs(startNode, endNode);
  9.    
  10.     // if we can't find anymore paths the flow will be 0
  11.     if(flow==0)
  12.     {
  13.       break;
  14.     }
  15.  
  16.     maxFlow +=flow;
  17.     int currentNode=endNode;
  18.    
  19.     // we update the passed flow matrix
  20.     while(currentNode != startNode)
  21.     {
  22.       int previousNode = parentsList[currentNode];
  23.       flowPassed[previousNode][currentNode] += flow;
  24.       flowPassed[currentNode][previousNode] -= flow;
  25.  
  26.       currentNode=previousNode;
  27.     }
  28. }
  29.  
  30. return maxFlow;
  31. }
Advertisement
Add Comment
Please, Sign In to add comment