Page 1 sur 1
[..] Algorithme de Ford
Posté : dim. 04 sept. 2011 20:04
par jcaspar
B 
onjour à tous !
Voici mes avancées ....je ne comprends pas bien la signification du pseudo code...
Merci d'avance pour votre aide et vos conseils !
Code : Tout sélectionner
#NoTrayIcon
#include <array.au3>
global $graphe,$sommet
global $sommet_initial=0
global $i=5,$j=5
global $arc[$i][$j]
global $poids_u,$poids_u_v,$poids_v
global $paux
global $pred_v
global $nbre_sommets
global $arc,$poids_u,$poids_v
global $arr
sommets()
arc()
ford()
_ArrayDisplay($arr)
Func sommets()
$nbre=InputBox("Nombre de sommets","Indiquer le nombre de sommets ",10)
For $nbre=0 to 1 step -1
MsgBox(64,"test",$nbre,5)
Next
;~ lister la valeur et le nom de tous les sommets
;~ Local $arr[3][3] = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]
;~ Local $i, $j
;~ For $i = 0 to UBound( $arr, 1) - 1
;~ For $j = 0 to UBound($arr, 2) - 1
;~ ConsoleWrite("$arr[" & $i & "][" & $j & "]:=" & $arr[$i][$j] & @LF)
;~ Next
;~ ConsoleWrite(@LF)
;~ Next
EndFunc
Func arc()
MsgBox(64,"Lister les arc",$arc,10)
EndFunc
Func ford()
For $i = 5 to 1 Step -1
ConsoleWrite($i)
Next
EndFunc
Re: [..] Algorithme de Ford
Posté : dim. 04 sept. 2011 20:06
par Tlem
J'ai édité votre code, afin de le rendre plus présentable.
Essayez d'utiliser Scite4AutoIt pour écrire votre code, car en utilisant la combinaison de touche CTRL + T, votre code aura une indentation plus correcte.
En ce qui concerne la résolution de votre problème, je ne puis vous aider, car je ne m'y connais pas du tout en algo.
Re: [..] Algorithme de Ford
Posté : dim. 04 sept. 2011 21:15
par mikell
Re: [..] Algorithme de Ford
Posté : dim. 04 sept. 2011 22:39
par Strofe
Bonsoir
Voici un début....
► Afficher le texte
Code : Tout sélectionner
;~ http://fr.wikipedia.org/wiki/Algorithme_de_Ford-Fulkerson
;~ http://www.math.u-psud.fr/~montcouq/Enseignements/Apprentis/distance.pdf
#NoTrayIcon
#include <array.au3>
Dim $nb
$nb = InputBox("Algorithme de Ford-Fulkerson", "Nombre de sommets : ", 5)
Global $d[$nb] ; "" = Infini
Global $P[$nb] ; "" = Nul
Global $G[$nb] ; Nom des sommets
Global $v[$nb][$nb] ; Distance entre deux sommets
;~ Initialise les variables
Init($nb)
$fini = False
Do
_ArrayDisplay($d)
_ArrayDisplay($P)
_ArrayDisplay($G)
_ArrayDisplay($v)
$fini = True ;Si c'est la fin..... ;-)
Until $fini
Func Init($nb)
For $i = 0 to $nb - 1
$d[$i] = ""
$P[$i] = ""
$G[$i] = InputBox("Nom du sommet",$i & " : ")
Next ; $i
$d[0] = 0
For $i = 0 to $nb - 1
For $j = $i+1 to $nb - 1
$v[$i][$j] = InputBox("Distance entre deux sommets","v(" & $G[$i] & ", " & $G[$j] & " ) = ")
Next ; $j
Next ; $i
EndFunc
Bon courage
Re: [..] Algorithme de Ford
Posté : lun. 05 sept. 2011 13:35
par jcaspar
Merci beaucoup !
Je vais voir ce que tu as fait ! Cela a déjà l'air très bien ...
Re: [..] Algorithme de Ford
Posté : lun. 05 sept. 2011 22:37
par Strofe
Re: [..] Algorithme de Ford
Posté : mar. 06 sept. 2011 22:18
par Strofe
Bonsoir
Alors pas motivé le demandeur
► Afficher le texte
Code : Tout sélectionner
;~ http://fr.wikipedia.org/wiki/Algorithme_de_Ford-Fulkerson
;~ http://www.math.u-psud.fr/~montcouq/Enseignements/Apprentis/distance.pdf
#NoTrayIcon
#include <array.au3>
Dim $nb
$nb = InputBox("Algorithme de Ford-Fulkerson", "Nombre de sommets : ", 4)
Global $S[$nb] ; Liste des sommets --> Sommet
Global $A[$nb][$nb] ; Distance entre deux sommets --> Arc
Global $M[2*$nb] ; Matrice de calculs
;~ Initialise les variables
Init($nb)
#cs
Global $S[4]=["A","B","C","D"]
Global $A[4][4]=[["",8,6,2],["","","",""],["",3,"",""],["",5,1,""]]
#ce
_ArrayDisplay($S,"Liste des sommets")
_ArrayDisplay($A,"Distance entre les sommets")
_ArrayDisplay($M,"Matrice de Calculs")
$fini = False
Do
$fini = True ;Si c'est la fin..... ;-)
For $x = 0 to $nb - 1
For $y = 0 to $nb - 1
If $A[$x][$y] <> "" Then ; Liaison existante
ConsoleWrite($M[$x] + $A[$x][$y] & " < " & $M[$y] & @CRLF)
If (($M[$x] + $A[$x][$y] < $M[$y]) OR ($M[$y]="")) Then
$M[$y] = $M[$x] + $A[$x][$y]
$M[$y+$nb] = $S[$x]
$fini = False ;Si c'est pas la fin..... ;-(
EndIf
EndIf
Next ; $y
Next ; $x
_ArrayDisplay($M,"Matrice Intermédiaire")
Until $fini
_ArrayDisplay($M,"Matrice finale")
Func Init($nb)
For $i = 0 to $nb - 1
$S[$i] = InputBox("Nom du sommet","N° " & $i & " : " )
Next ; $i
For $i = 0 to $nb - 1
For $j = 0 to $nb - 1
$A[$i][$j] = InputBox("Distance entre deux sommets","v(" & $S[$i] & ", " & $S[$j] & " ) = "& @CRLF & @CRLF & "vide pour infini --> Pas d'arc")
Next ; $j
Next ; $i
For $i =0 to (2*$nb) - 1
$M[$i] =""
Next ; $i
$M[0] =0
EndFunc
Re: [..] Algorithme de Ford
Posté : mer. 21 sept. 2011 16:49
par jcaspar
Merci beaucoup pour les informations et le code fourni
Je vais potasser cela ( actuellement je sui un peu overbooké lol )
Re: [..] Algorithme de Ford
Posté : jeu. 12 juil. 2012 00:09
par jcaspar
Trop fort ! Mais je me demande si il serait possible d'utiliser un udf pour représenter les sommets et les arcs
► Afficher le texte
Code : Tout sélectionner
;~ http://fr.wikipedia.org/wiki/Algorithme_de_Ford-Fulkerson
;~ http://www.math.u-psud.fr/~montcouq/Enseignements/Apprentis/distance.pdf
#NoTrayIcon
#include <array.au3>
Dim $nb
$nb = InputBox("Algorithme de Ford-Fulkerson", "Nombre de sommets : ", 4)
Global $S[$nb] ; Liste des sommets --> Sommet
Global $A[$nb][$nb] ; Distance entre deux sommets --> Arc
Global $M[2*$nb] ; Matrice de calculs
;~ Initialise les variables
Init($nb)
#cs
Global $S[4]=["A","B","C","D"]
Global $A[4][4]=[["",8,6,2],["","","",""],["",3,"",""],["",5,1,""]]
#ce
_ArrayDisplay($S,"Liste des sommets")
_ArrayDisplay($A,"Distance entre les sommets")
_ArrayDisplay($M,"Matrice de Calculs")
$fini = False
Do
$fini = True ;Si c'est la fin..... ;-)
For $x = 0 to $nb - 1
For $y = 0 to $nb - 1
If $A[$x][$y] <> "" Then ; Liaison existante
ConsoleWrite($M[$x] + $A[$x][$y] & " < " & $M[$y] & @CRLF)
If (($M[$x] + $A[$x][$y] < $M[$y]) OR ($M[$y]="")) Then
$M[$y] = $M[$x] + $A[$x][$y]
$M[$y+$nb] = $S[$x]
$fini = False ;Si c'est pas la fin..... ;-(
EndIf
EndIf
Next ; $y
Next ; $x
_ArrayDisplay($M,"Matrice Intermédiaire")
Until $fini
_ArrayDisplay($M,"Matrice finale")
Func Init($nb)
For $i = 0 to $nb - 1
$S[$i] = InputBox("Nom du sommet","N° " & $i & " : " )
Next ; $i
For $i = 0 to $nb - 1
For $j = 0 to $nb - 1
$A[$i][$j] = InputBox("Distance entre deux sommets","v(" & $S[$i] & ", " & $S[$j] & " ) = "& @CRLF & @CRLF & "vide pour infini --> Pas d'arc")
Next ; $j
Next ; $i
For $i =0 to (2*$nb) - 1
$M[$i] =""
Next ; $i
$M[0] =0
EndFunc
[/quote]
