Post on 12-Nov-2018
L'algoritmo di Ford-Fulkerson:un esempio di applicazione
Prof. Giancarlo Ferrari Trecate
Dipartimento di Informatica e Sistemistica
Università degli Studi di Pavia
giancarlo.ferrari@unipv.it
Rappresentazione della rete incrementale
i ja b
a: capacità residua dell'arco direttob: capacità residua dell'arco inverso
i j
b
a
⇔
Nodo di partenza:
Archi diretti e inversi:
s0
0 : valore del flusso
Problema
4
6
2
3
1 5 7
9
12
3
6
9
4
63
2
2
25
8
7
Determinare il flusso massimo dal nodo s=1 al nodo t=7 nella rete seguente:
Inizializzazione
4
6
2
3
1 5 79
0
0
12
6
0
0
3
03
90
4
0 0
2
2
0
8 0
0
0
7
5
0
2
60
Le capacità degli archi inversi sono pari alle capacità della rete di partenza
0
Iterazione 1
4
6
2
3
1 5 79
0
0
12
6
0
0
3
03
90
4
0 0
2
2
0
8 0
0
0
7
5
0
2
60
● Cammino aumentante P:1247● Massimo incremento di flusso:
0
=7
Iterazione 1
4
6
2
3
1 5 72
7
0
12
6
0
0
3
03
27
4
0 0
2
2
0
8 0
7
0
0
5
0
2
60
7
● Aggiornamento delle capacità lungo P e del valore del flusso● Osservazione: l'arco (4,7) e' saturo
Iterazione 2
4
6
2
3
1 5 72
7
0
12
6
0
0
3
03
27
4
0 0
2
2
0
8 0
7
0
0
5
0
2
60
7
● Cammino aumentante P:1367● Massimo incremento di flusso: =3
Iterazione 2
4
6
2
3
1 5 72
7
3
9
6
3
0
3
00
27
4
0 0
2
2
0
8 0
7
3
0
2
0
2
60
10
● Aggiornamento delle capacità lungo P e del valore del flusso● Osservazione: l'arco (3,6) e' saturo
Iterazione 3
4
6
2
3
1 5 72
7
3
9
6
3
0
3
00
27
4
0 0
2
2
0
8 0
7
3
0
2
0
2
60
10
● Cammino aumentante P:1357● Massimo incremento di flusso: =6
Iterazione 3
4
6
2
3
1 5 72
7
9
3
6
3
0
3
00
27
4
0 0
2
2
0
2 6
7
3
0
2
0
2
06
16
● Aggiornamento delle capacità lungo P e del valore del flusso● Osservazione: l'arco (3,5) e' saturo
Iterazione 4
4
6
2
3
1 5 72
7
9
3
6
3
0
3
00
27
4
0 0
2
2
0
2 6
7
3
0
2
0
2
06
16
● Cammino aumentante P:12457● Massimo incremento di flusso: =2
Iterazione 4
4
6
2
3
1 5 70
9
9
3
6
3
0
3
00
09
4
0 2
0
2
0
0 8
7
3
0
2
0
2
06
18
● Aggiornamento delle capacità lungo P e del valore del flusso● Osservazione: l'arco (4,5) e' saturo
Iterazione 5
4
6
2
3
1 5 70
9
9
3
6
3
0
3
00
09
4
0 2
0
2
0
0 8
7
3
0
2
0
2
06
18
● Cammino aumentante P:1342567● Massimo incremento di flusso: ● E' stato utilizzato l'arco inverso (4,2)
=2
Iterazione 5
4
6
2
3
1 5 70
9
11
1
6
3
0
3
00
27
2
2 2
0
0
2
0 8
7
5
0
0
2
0
06
20
● Aggiornamento delle capacità lungo P e del valore del flusso● Osservazione: tutti gli archi che arrivano al nodo 7 sono saturi ⇒ Non puo' esistere nessun un cammino aumentante, neppure utilizzando archi inversi.
Iterazione 5
4
6
2
3
1 5 70
9
11
1
6
3
0
3
00
27
2
2 2
0
0
2
0 8
7
5
0
0
2
0
06
20
L'algoritmo si arresta ed il valore del flusso ottimo e' pari a 20