Adaptation de Bellman pour le reseau d'ecart
[mist@savage mroProject]$ diff BellmanFord.py BFForFF.py
1 1,2c1,2
2 < # Bellman-Ford simple algorithm
3 < # copyright 20040526 Strasser Michel
4 ---
5 > # Bellman-Ford simple algorithm for Ford-Fulkerson
6 > # copyright 20040527 Strasser Michel
7 4c4
8 < class BellmanFord:
9 ---
10 > class BFForFF:
11 20c20,21
12 < if((j.fromV.bfWeight + j.cost) < j.toV.bfWeight):
13 ---
14 > # if j is not saturated, the network has an arc valuated with j.cost
15 > if((j.cUPlus()>0) and ((j.fromV.bfWeight + j.cost) < j.toV.bfWeight)):
16 21a23,24
17 > j.toV.bfPrevArc=j
18 > j.toV.bfPrevArcType=2
19 22a26,32
20 > for j in self.graph.arcsList:
21 > # if j has a non null flow, the network has an -j arc valuated with -j.cost
22 > if((j.cUMin()>0) and ((j.toV.bfWeight - j.cost) < j.fromV.bfWeight)):
23 > j.fromV.bfPrev=j.toV
24 > j.fromV.bfPrevArc=j
25 > j.fromV.bfPrevArcType=1
26 > j.fromV.bfWeight=j.toV.bfWeight - j.cost
27 29a40
28 > print "Way : "
29 32a44,45
30 > prev.bfNextArc=v.bfPrevArc
31 > prev.bfNextArcType=v.bfPrevArcType
32 33a47
33 > print "-> ", v.id
- Si l'arc j n'est pas saturé, le réseau d'écart a un arc j valué à coût(j)
- Si l'arc j a un flot non nul, le réseau décart a un arc -j valué à -coût(j)
On garde aussi la connaissance de quel type d'arc il s'agit à chaque fois, cela
nous sera utile pour la suite.
index
