Algorithme de Bellman
[mist@savage bellman]$ ls
CoursCout.dia CoursCout.grh CoursCout.png
[mist@savage bellman]$ cat ../BellmanFord.py
1 # Bellman-Ford simple algorithm
2 # copyright 20040526 Strasser Michel
3
4 class BellmanFord:
5
6 def __init__(self, graph):
7 self.graph=graph
8 self.s=self.graph.verticesHash["SOURCE"]
9 self.p=self.graph.verticesHash["SINK"]
10
11 def do(self):
12 for i in self.graph.verticesList:
13 i.bfWeight=10000000 # initialising every weights to +infinite
14 i.bfNext=0 # next is nil
15 i.bfPrev=0 # previous is nil
16 self.s.bfWeight=0 # source weight is 0
17
18 for i in range(0, len(self.graph.verticesList)):
19 for j in self.graph.arcsList:
20 if((j.fromV.bfWeight + j.cost) < j.toV.bfWeight):
21 j.toV.bfPrev=j.fromV
22 j.toV.bfWeight=j.fromV.bfWeight + j.cost
23
24 # creating best way
25 v=self.p
26
27 if(v.bfPrev==0):
28 return False
29
30 while(v != self.s):
31 prev=v.bfPrev
32 prev.bfNext=v
33 v=prev
34
35 return True
[mist@savage bellman]$ display CoursCout.png
[mist@savage bellman]$ python ../bellman.py CoursCout.grh out.grh
GrhReader .graph='Graph .arcsList=[Arc .fromV='SOURCE' .toV='1' .flow='0.0' .cap acity='2.0' .cost='1.0', Arc .fromV='SOURCE' .toV='2' .flow='0.0' .capacity='1.0 ' .cost='40.0', Arc .fromV='1' .toV='2' .flow='0.0' .capacity='3.0' .cost='1.0', Arc .fromV='2' .toV='4' .flow='0.0' .capacity='3.0' .cost='1.0', Arc .fromV='4' .toV='SINK' .flow='0.0' .capacity='1.0' .cost='100.0', Arc .fromV='1' .toV='4' .flow='0.0' .capacity='5.0' .cost='20.0', Arc .fromV='SOURCE' .toV='4' .flow='0. 0' .capacity='4.0' .cost='3.0', Arc .fromV='3' .toV='SINK' .flow='0.0' .capacity ='1.0' .cost='1.0', Arc .fromV='2' .toV='3' .flow='0.0' .capacity='3.0' .cost='4 0.0', Arc .fromV='4' .toV='3' .flow='0.0' .capacity='2.0' .cost='1.0', Arc .from V='2' .toV='SINK' .flow='0.0' .capacity='4.0' .cost='40.0']'
[mist@savage bellman]$ xmllint --format out.grh > out2.grh
[mist@savage bellman]$ cat out2.grh
1 <?xml version="1.0"?>
2 <!--This is a generated document, STRASSER Michel's MRO project 20040503-->
3 <graph>
4 <arc from="SOURCE" to="1" flow="0.0" capacity="2.0" cost="1.0"/>
5 <arc from="SOURCE" to="2" flow="0.0" capacity="1.0" cost="40.0"/>
6 <arc from="1" to="2" flow="0.0" capacity="3.0" cost="1.0"/>
7 <arc from="2" to="4" flow="0.0" capacity="3.0" cost="1.0"/>
8 <arc from="4" to="SINK" flow="0.0" capacity="1.0" cost="100.0"/>
9 <arc from="1" to="4" flow="0.0" capacity="5.0" cost="20.0"/>
10 <arc from="SOURCE" to="4" flow="0.0" capacity="4.0" cost="3.0"/>
11 <arc from="3" to="SINK" flow="0.0" capacity="1.0" cost="1.0"/>
12 <arc from="2" to="3" flow="0.0" capacity="3.0" cost="40.0"/>
13 <arc from="4" to="3" flow="0.0" capacity="2.0" cost="1.0"/>
14 <arc from="2" to="SINK" flow="0.0" capacity="4.0" cost="40.0"/>
15 <vertex id="SOURCE" x="9.0" y="12.0" bfNext="1"/>
16 <vertex id="1" x="18.0" y="13.0" bfPrev="SOURCE" bfNext="2"/>
17 <vertex id="SINK" x="40.0" y="18.0" bfPrev="3"/>
18 <vertex id="2" x="19.0" y="24.0" bfPrev="1" bfNext="4"/>
19 <vertex id="4" x="29.0" y="9.0" bfPrev="2" bfNext="3"/>
20 <vertex id="3" x="29.0" y="15.0" bfPrev="4" bfNext="SINK"/>
21 </graph>
[mist@savage bellman]$
index
