orchidmajumder's blog

By orchidmajumder, 9 years ago, In English

Hi,

I want to ask that while initializing the potential array for all the nodes in min cost max flow (edmond karp +djikstra potential method) should I initialize all with zero like what is described in the network flow book by ahuja(same is done also in egor's code) or should I run a bellman ford to set those initial values like what's described in topcoder tutorial min Cost Max Flow successive shortest path algorithm???
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That depends on whether your graph contains negative cost edges from the start or not. If it does then you must run Bellman-Ford (or another single source shortest path distance algorithm capable of handling negative edges) and set the potentials accordingly. If it doesn't then there's no need to run an initial Bellman-Ford, although there's no harm in doing it (apart from some extra runtime and code).