[R] Algorithme de Ford

[jcaspar]

B onjour à tous !

Je souhaiterais convertir l'algorithme de Ford (Theorie des graphes) en programme autoit ci dessous
voici le pseudo code l'idéal serait de parvenir à un petit programme ou l'on entre le nom de tous les arcs et leurs valeurs afin d'obtenir le chemin le plus court.

Pourriez vous svp m'aider à réaliser ce programme ? Ci dessous ce que j'ai compris ...
( Je ne comprends pas très bien le pseudo code ...mais avec votre aide cela devrait être relativement facile à mettre en oeuvre )

Merci d'avance pour votre aide et vos conseils


booléen Bellman_Ford(G, s)

initialisation (G, s) // les poids de tous les sommets sont mis à +infini
// le poids du sommet initial à 0
pour i=1 jusqu'à Nombre de sommets -1 faire
| pour chaque arc (u, v) du graphe faire
| | paux := poids(u) + poids(arc(u, v));
| | si paux < poids(v) alors
| | | pred(v) := u;
| | | poids(v) := paux;
pour chaque arc (u, v) du graphe faire
| si poids(u) + poids(arc(u, v)) < poids(v) alors
| retourner faux
retourner vrai

Code : Tout sélectionner

 

   #NoTrayIcon

   global $g,$s=0,$i,$u,$p,$nbre

   inputbox("Entrer nombre de sommets","Nbre sommets","")
   inputbox("Entrer la valeur du Premier sommet")
   inputbox("Entrer la valeur du Second Sommet")
    ;~ lister la valeur et le nom de tous les sommets




function ford(p,u,v)

for $i =1 to $nbre-1
$p+$u


        next

end func
 

[Habibsbib]

Coucou,
Je vois que tu as commencé mais tu n'as pas fait grand chose.
L'algo que tu donnes est copié\collé de Wikipédia en plus, je pense que tu aurais pu faire un effort...

Voilà un algorithme de PathFinding en AutoIt que j'ai fait il y a pas mal de temps maintenant, tu peux t'en servir à la place de Ford qui a priori n'est pas particulièrement avantageux, sauf si tu as vraiment de très grandes maps à traiter (je te préviens, j'ai la flemme de repasser dessus et c'est "CACA" mais ça marche) :

Code : Tout sélectionner

#include <Array.au3>

Global $end_pos[2] = [7, 2]
Global $xy[2] = [0, 4], $last
Global $path, $lastvar, $lowweight
Global $maplimit[2] = [7, 7] ;coordonnée_maximale x|coordonnée_maximale y
Global $mapbar[6] = ["2|1", "2|2", "2|3", "4|4", "5|1", "5|2"] ;coordonnées des cases obstacles
Global $barstring

_GetPath()

Func _GetPath()
   Do
      _Execute()
   Until _IsEndPath()
   MsgBox(0, "", $path)
EndFunc   ;==>_GetPath

Func _IsEndPath()
   If $xy[0] = $end_pos[0] And $xy[1] = $end_pos[1] Then
      Return True
   Else
      Return False
   EndIf
EndFunc   ;==>_IsEndPath

Func _Execute()
   $last = $xy
   Global $coord[8] = ["", "", "", "", "", "", "", ""]
   $coord[0] = ($xy[0] - 1) & "|" & $xy[1] ;gauche
   $coord[1] = ($xy[0] + 1) & "|" & $xy[1] ;droite
   $coord[2] = $xy[0] & "|" & ($xy[1] - 1) ;haut
   $coord[3] = $xy[0] & "|" & ($xy[1] + 1) ;bas
   $coord[4] = ($xy[0] + 1) & "|" & ($xy[1] + 1) ;diagonale droite basse
   $coord[5] = ($xy[0] + 1) & "|" & ($xy[1] - 1) ;diagonale droite haute
   $coord[6] = ($xy[0] - 1) & "|" & ($xy[1] - 1) ;diagonale gauche haute
   $coord[7] = ($xy[0] - 1) & "|" & ($xy[1] + 1) ;diagonale gauche basse

   For $i = 0 To 7
      Global $x = _StringLeft($coord[$i], "|")
      Global $y = _StringRight($coord[$i], "|")

      If 0 <= $x And $x <= $maplimit[0] And 0 <= $y And $y <= $maplimit[1] Then
         If Not _BlockedCase($x, $y) And Not _Crossed($x, $y) Then
            $coord[$i] = $coord[$i] & "P" & _GetWeight($x, $y)
         Else
            $coord[$i] = $coord[$i] & "P" & (6 * 10 ^ 3)
         EndIf
      Else
         $coord[$i] = $coord[$i] & "P" & (6 * 10 ^ 3)
      EndIf
   Next

   $lastvar = $coord[0]
   $lowweight = 0
   For $i = 1 To 7
      If Number(_StringRight($lastvar, "P")) > Number(_StringRight($coord[$i], "P")) Then
         $lowweight = $i
         $lastvar = $coord[$i]
      EndIf
   Next

   $firstdub = _StringLeft($coord[$lowweight], "P")
   $middub = StringSplit($firstdub, "|")
   $xy[0] = $middub[1]
   $xy[1] = $middub[2]
   $path = $path & "|" & $xy[0] & ";" & $xy[1]
EndFunc   ;==>_Execute

Func _Crossed($x, $y)
   If StringInStr($path, $x & ";" & $y) Then
      Return True
   Else
      Return False
   EndIf
EndFunc   ;==>_Crossed

Func _GetWeight($radx, $rady)
   $calcrat = ($end_pos[0] - $radx) ^ 2 + ($end_pos[1] - $rady) ^ 2
   $calcmid = Sqrt($calcrat)
   $calxrat = (($xy[0] - $radx) ^ 2 + ($xy[1] - $rady) ^ 2)
   $calxmid = Sqrt($calcrat)
   Return ($calcmid + $calxmid)
EndFunc   ;==>_GetWeight

Func _StringLeft($str, $limit)
   $dstr = StringSplit($str, $limit)
   Return $dstr[1]
EndFunc   ;==>_StringLeft

Func _StringRight($str, $limit)
   $dstr = StringSplit($str, $limit)
   Return $dstr[2]
EndFunc   ;==>_StringRight

Func _BlockedCase($xar, $yar)
   _ArraySearch($mapbar, $xar & "|" & $yar)
   If Not @error Then
      Return True
   Else
      Return False
   EndIf
EndFunc   ;==>_BlockedCase
 

J'étais sensé rajouter un petit truc pour dire si aucun chemin n'était possible, mais là j'ai la flemme donc c'est à toi de bidouiller si ça t'intéresse.

Cordialement,

[Zippo]

Ce post a un an Habibsbib

[Habibsbib]

Oups.