HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is this flow a max flow?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thiswhymaxflow

Problem

According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how can this be the max flow?

Solution

You've left out part of the statement. It should be "If there's no path between the source and the sink with unused capacity the flow is a max flow." If you look at your graph you'll see that there is no path with unused capacity all the way from $s$ to $t$. The $s$ to $a$ link has spare capacity but $a$'s lone outbond link is saturated. The $s$ to $c$ link is saturated.

Context

StackExchange Computer Science Q#43269, answer score: 6

Revisions (0)

No revisions yet.