Simulator Ford-Fulkerson

Retea cu 3 surse si 3 destinatii. Standardizare, incarcare initiala, redistribuire, drum eliberat si taietura minima - pas cu pas.

Configurarea experimentului

Fiecare retea are 3 surse I1-I3, 3 destinatii D1-D3 si noduri de tranzit. Generarea schimba atat structura grafului (arcele existente), cat si capacitatile. Pentru compararea celor doua ordini, selectia ordinii nu modifica reteaua generata.

Capacitate liberaArc saturatArc incarcatFlux retras (arc invers)Taietura minima

Eticheta unui arc este flux / capacitate. Capacitatile sunt unitati de transport pe ora, date ale retelei, nu distante geometrice. S si T apar dupa standardizare.

Istoricul pasilor

Ce se intampla la fiecare etapa?

  1. Forma initiala: cele trei surse si cele trei destinatii sunt distincte.
  2. Standardizare: adaugam supersursa S si superdestinatia T. Arcele S-Ii limiteaza oferta; arcele Dj-T limiteaza receptia.
  3. Etapa I: incarcam drumurile directe S-T in ordinea aleasa. Delta este minimul capacitatilor reziduale de pe drum.
  4. Etapa II: daca nu mai exista drum direct, cautam un lant rezidual care poate contine arce inverse. Mai intai aratam redistribuirea (fluxul retras), apoi incarcarea drumului eliberat (cresterea neta a fluxului). Valorile intermediare din primul subpas sunt o previzualizare; fluxul fezabil este actualizat atomic la al doilea subpas.
  5. Final: cand T nu mai este accesibil in reteaua reziduala, nodurile accesibile formeaza partea V a taieturii minime, restul formeaza W. Capacitatea taieturii este egala cu fluxul maxim.

Ordinea de explorare poate modifica fluxul obtinut dupa Etapa I si numarul de redistribuiri. Fluxul maxim final ramane acelasi pentru aceeasi retea.