# Modifying Dijkstra's Algorithm for Max Flow

Page 1 of 1

## 5 Replies - 4748 Views - Last Post: 08 December 2012 - 09:16 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=302907&amp;s=261cdb5207dae0359222bf5ee9e5745e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 JavaLilly

Reputation: 0
• Posts: 30
• Joined: 05-September 12

# Modifying Dijkstra's Algorithm for Max Flow

Posted 05 December 2012 - 07:14 PM

This is an assignment. I am trying to convert Dijkstra's algorithm into a max flow problem by changing Dijkstra's algorithm to focus on flows instead of distance. Then I tried to take the relax edge method and implement it in Ford Fulkerson's has augmenting path.

I tried implementing the relax in edge in Ford Fulkerson. I tried to substitute it for has augmenting path, but I couldn't get the parameters quite right. So then I tried putting it into the has augmenting path which is what I put below. Logically, it makes sense to me, but I keep getting an Illegal Increase exception and I don't know why. Could you point me in the right direction? I thought maybe it was saying that because I was trying to relax an edge and increase the index when I wasn't supposed to, but I am still confused.

// is there an augmenting path?
// if so, upon termination edgeTo[] will contain a parent-link representation of such a path
private boolean hasAugmentingPath(FlowNetwork G, int s, int t) {
edgeTo = new FlowEdge[G.V()];
marked = new boolean[G.V()];

IndexMaxPQ<Double> q = new IndexMaxPQ<Double>(G.V());
q.insert(s, Double.POSITIVE_INFINITY);
marked[s] = true;
while (!q.isEmpty()) {
int v = q.delMax();

for (FlowEdge e : G.adj(v)) {
int w = e.other(v);

//  if residual capacity from v to w
if (e.residualCapacityTo(w) > 0) {
/**
q.insert(w, e.flow());
edgeTo[w] = e;
System.out.println(e);
**/

marked[w] = true;
double flowKeep = e.flow();// = 0.0; //keeps track of the current flow on an edge
if (flowKeep < e.capacity()) { // the flow on the FlowEdge is greater than the flow on that before it
flowKeep = e.capacity();//set flowKeep to that new edge
edgeTo[w] = e;//make edge to w the new "last edge" looked at
if (q.contains(w)) q.decreaseKey(w, flowKeep);
else                q.insert(w, flowKeep);
}
}

}
}

// is there an augmenting path?
return marked[t];
}

Is This A Good Question/Topic? 0

## Replies To: Modifying Dijkstra's Algorithm for Max Flow

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11248
• Posts: 42,314
• Joined: 27-December 08

## Re: Modifying Dijkstra's Algorithm for Max Flow

Posted 07 December 2012 - 10:50 PM

Dijkstra's algorithm really isn't practical to use for flow maximization. Ford-Fulkerson is a completely different algorithm. This is how it works:

-Start at A and do a BFT on its children
-For each child
-If flow < capacity
-Mark it with (A as the parent, + for going forward, capacity - flow)
-Push the label onto the queue

-While the sink Z hasn't been reached and there are augmentable edges:
-Poll an element from the queue, call it C
-For each child of c:
-If the forward flow < capacity
Mark it with (C as the parent, + for going forward, Min(capacity - flow, flow into C))
-Push the label onto the queue
-Else if the backward flow > 0
-Mark the edge with (C as the parent, - for going backwards, Min(edge flow into the current child, flow into C)
-Push the label onto the queue

-Augment the vertices based on the path of C and repeat from A

I don't see things like handling backwards flow in your implementation.

### #3 JavaLilly

Reputation: 0
• Posts: 30
• Joined: 05-September 12

## Re: Modifying Dijkstra's Algorithm for Max Flow

Posted 08 December 2012 - 08:36 PM

Thank you, I am going to try this out. You explanation makes a lot of sense.
I hadn't thought about looking at backward flow. Why would I need to though? If I find the flow going one way, do I need to double check it?

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11248
• Posts: 42,314
• Joined: 27-December 08

## Re: Modifying Dijkstra's Algorithm for Max Flow

Posted 08 December 2012 - 08:37 PM

What happens is if you have additional flow coming into a vertex, it can push flow back and direct it along another path, thus augmenting the flow. It re-routes the flow.

### #5 JavaLilly

Reputation: 0
• Posts: 30
• Joined: 05-September 12

## Re: Modifying Dijkstra's Algorithm for Max Flow

Posted 08 December 2012 - 08:59 PM

So if I have (where s is my source and t is my sink),
/ --- w \
s -----|--t
\ --- v /

The backward flow I need to calculate into w would be the effect of the flow coming in from v and from s?

This post has been edited by JavaLilly: 08 December 2012 - 09:00 PM

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11248
• Posts: 42,314
• Joined: 27-December 08

## Re: Modifying Dijkstra's Algorithm for Max Flow

Posted 08 December 2012 - 09:16 PM

Think about it this way: If you have flow from A -> B and C -> B, you could push the flow from A -> B back from B -> C, then from C to other vertices.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }