Scribd
Upload
70 views8 pages

Flow Problem: Muhammad Saadi, PH.D

This document provides an overview of the Ford-Fulkerson algorithm for finding the maximum flow in a flow network. It includes examples of original networks and their optimal flows found using Ford-Fulkerson. Key terms discussed include residual networks and augmented paths. The document is presented as a lecture on flow problems and the Ford-Fulkerson algorithm.

Uploaded by

Ehsan Abid Hassan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
70 views8 pages

Flow Problem: Muhammad Saadi, PH.D

This document provides an overview of the Ford-Fulkerson algorithm for finding the maximum flow in a flow network. It includes examples of original networks and their optimal flows found using Ford-Fulkerson. Key terms discussed include residual networks and augmented paths. The document is presented as a lecture on flow problems and the Ford-Fulkerson algorithm.

Uploaded by

Ehsan Abid Hassan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Lecture

Flow Problem
Muhammad Saadi, Ph.D.
Assistant Professor
Department of Electrical Engineering
University of Central Punjab
Ford-Fulkerson Algorithm

2
0,10 0,8

s 0,1 t

0,6 0,10
4
Optimal Flow

2
9 8

s 1 t

6 7
4
Ford-Fulkerson Max Flow
4
2 5
3 1 1 1
2 2
s 4 t
3 2
1

3
This is the original network
Ford-Fulkerson Max Flow
1
2 5
1 1
2 2
s 4 t
2 2

3
Here is the optimal flow
7 Ford-Fulkerson Algorithm
8 Max Flow Example

6 • Try Ford-Fulkerson
B D
5 6 greedy approach

• What if we do
A F some non greedy
3 approach
3 6
5
C 1 E
9 Some more terms

What is Residual Network?


What is Augmented Paths?

You might also like