047 Algoritmul Bellman-Ford

[•Marius]

Aici puteţi discuta despre problema Algoritmul Bellman-Ford.

[•xtreme]

De ce nu comentati sursele alea de 100 de puncte? Puneti tot felul de functii complicate ca sa nu se inteleaga algoritmul in sine.Probabil ca e mai eficient dar e mai bine sa sacrificam pentru simplitate, pentru ca dupa ce intelegi algoritmul si stii si functiile alea "smechere" o sa fie foarte usor sa il optimizezi.

[•CezarMocan]

Care sunt functiile astea complicate? 

[•wefgef]

@xtreme: Eu cred ca poti sa te exprimi si mai frumos, tu ce zici? Ia incearca.

@cezer: Probabil se refera la STL. Si eu sunt de parere ca sursele oficiale contin prea mult STL in ele.

Ar trebui sa stabilim un standard pentru sursele oficiale din arhiva educationala. Poate vom discuta asta la urmatoarea sedinta.

[•gabitzish1]

Am propus si eu chestia asta unor membri din echipa. Cred ca sursele care se dau ca model ar trebui sa fie cat mai aranjate si comentate.
Scopul lor (in viziunea mea) e sa clarifice algoritmul, sa ajute la intelegerea lui, nu sa scoata in evidenta dibacia celui ce'a scris'o. Cred ca niste surse aerisite ca aspect si clarificate prin comentarii ar ajuta mai multa lume.

[•xtreme]

Eu zic ca modul de redactare a sursei http://infoarena.ro/job_detail/381834?action=view-source e groaznic.Functiile assert ajuta doar la debugging, dupa ce ne-am asigurat ca programu trece testele aceste functii nu mai au sens.Pentru un tip care vrea sa-nvetze algoritmul, folosirea vectorului adj_t este inutila(probabil ca l-a ajutat pe el la rezolvare).Cand ia toate muchiile care pornesc dintr-un nod pe care tocmai l-a scos din coada verifica daka acest nod i-a fost calculata distanta(dist[nodcur]<INF), aceeasta conditie e intotdeauna adevarata pentru ca nu bagi in coada numai nodurile a caror distanta a fost calculata.Codul pare a fi scris in graba ca si multe alte surse exemplare din arhiva educationala. 

[•alexandru92]

assert este folosit pentru a testa testele, daca se incadreaza in limitele  mentionate mai sus.

[•xtreme]

@alexandru :De unde esti? .Precis daca nu spuneai tu nu stiam, nu se subintelege din posturile mele anterioare ca stiam asta? 
@pentru restu Autorul a fost scump la comentarii , poate sa ma lamureasca cineva de ce e ciclu infinit daca se introduce de N+1 ori acelasi nod in coada?

[•pauldb]

Ce zici sa adopti un ton mai politicos? Contrar asteptarii tale, echipa infoarena nu are nici o indatorire in a te ajuta, ce facem noi este munca voluntara. Daca nu iti place cum ne facem treaba si nu stii sa te integrezi frumos in comunitate, poti sa inveti programare in alta parte.

Noi iti oferim un model la aceste probleme, dar toate problemele au sursa libera. Daca vreun aspect nu ti-e clar, poti sa studiezi si ce au facut altii.

[•Mishu91]

Eu zic ca modul de redactare a sursei [...] e groaznic.

Să nu ne obrăznicim. Dacă o sursă este redactată într-un stil diferit de al tău nu înseamnă că este groaznică.

@pentru restu Autorul a fost scump la comentarii , poate sa ma lamureasca cineva de ce e ciclu infinit daca se introduce de N+1 ori acelasi nod in coada?

Dacă ai fi citit explicațiile de pe wiki (din articolul către care se face legătura), ai fi aflat de ce e așa. Consider ca nu trebuie făcută muncă de transcriere dacă există niște articole deja scrise.

[•toni2007]

Eu zic ca modul de redactare a sursei [...] e groaznic.

Sursa oficiala e codata dupa standard, ce codezi tu nu este dupa standard . Eu as zice mai degraba sa inveti tu sa indentezi, decat sa critici. Eu sincer nu prea iti inteleg sursele.

[•Marius]

Eu zic ca modul de redactare a sursei http://infoarena.ro/job_detail/381834?action=view-source e groaznic.Functiile assert ajuta doar la debugging, dupa ce ne-am asigurat ca programu trece testele aceste functii nu mai au sens.Pentru un tip care vrea sa-nvetze algoritmul, folosirea vectorului adj_t este inutila...

Nu te supăra, dar eu când am învăţat aceşti algoritmi de bază nu am avut niciun model de sursă şi tare aş fi vrut să am, de orice fel ar fi fost ea.

@wefgef Nu ştiu dacă mult STL strică. Nu e deloc greu să cauţi în documentaţie, iar dacă te obişnuieşti cu el atunci nu ai decât de câştigat.

LE: Acum ştiu de ce îmi tot scădea Karma.

[•APOCALYPTO]

Salut!
Cu execeptia primului si a ultimului nod din ciclu restul trebuie sa nu se repete(sa fie distincte)?

[•Marius]

Salut!
Cu execeptia primului si a ultimului nod din ciclu restul trebuie sa nu se repete(sa fie distincte)?

Da

[•philip]

Testele din atasamente sunt aceleasi cu cele din raportul evaluatorului (http://infoarena.ro/job_detail/407086)?
Daca verific manual, primesc aceleasi rezultate ca in atasamente, dar evaluatorul imi da incorect la majoritatea testelor.

[•dead_knight]

Cine nu înţelege sursa oficială puteţi să vă uitaţi la sursa asta http://infoarena.ro/job_detail/432233?action=view-source .
Am încercat să explic pe înţelesul tuturor.

[•S7012MY]

A incercat cineva sa implementeze varianta din introducere in algoritmi? Eu am incercat si nu stiu de ce nu imi da bine pe nici un exemplu.  

Cod:

#include <cstdio>
#include <cstring>
#define INFI 0x3f3f3f3f
#define DM 250001
#define DN 50001

struct nod {
    int x,cost;
    nod *urm;
}*v[DN];

int m,n,dist[DN],pr[DN];

void adaugare(int x,int y,int cost) {
    nod *p;
    p=new nod;
    p->cost=cost;
    p->x=y;
    p->urm=v[x];
    v[x]=p;
}

void relaxare(int u,int v,int cost) {
    if(dist[v]>dist[u]+cost) {
        dist[v]=dist[u]+cost;
        pr[v]=u;
    }
}

bool bellman_ford() {
    int i;
    nod *p;
    for(i=1; i<n; i++)
       for(p=v[i]; p!=NULL; p=p->urm)
            relaxare(i,p->x,p->cost);
    for(i=1; i<n; i++) for(p=v[i]; p!=NULL; p=p->urm)
        if(dist[i]>dist[p->x]+p->cost) return false;
    return true;
}

void initializareSU() {
    memset(dist,INFI,sizeof(dist));
    memset(pr,0,sizeof(pr));
    dist[1]=0;
}

void afisare() {
    nod *p;
    int k;
    for(k=1; k<=n; k++) {
        p=v[k];
        printf("%d:",k);
        while(p) {
            printf("%d ",p->x);
            p=p->urm;
        }
        printf("\n");
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int i,x,y,c;
    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++)
        scanf("%d %d %d",&x,&y,&c), adaugare(x,y,c);
    initializareSU();
    if(!bellman_ford()) printf("Ciclu negativ!\n");
    else for(i=2; i<=n; i++) printf("%d ",dist[i]);
    //afisare();
    return 0;
}

[•PlayLikeNeverB4]

Nu stiu ce ai facut tu acolo cu lista vecinilor, dar e ceva mult mai complicat decat e nevoie... sau poate nu inteleg eu Am vazut ca faci coada alocata dinamic, mie mi-a mers si static. De asemenea... long?

[•toni2007]

Problema e open-tests. Uite-te pe teste.

[•mrares]

Am implementat bellman ford cu coada cu liste si a aparut o problema...
Structura e

Cod:

struct lista
{
    int inf,c;
    lista *nod;
} *g[nmax];

si nmax din ce stiu eu inseamna numarul de noduri... si 1 ≤ N ≤ 50 000 din enunt. cu 50 005 iau killed by signal, cu m ( 250 005 ) pus iau la fel killed by signal, bea cu 500 005 iau 100 puncte. E gresit in enunt sau problema este de la mine? Tot ce am modificat a fost doar nmaxul respectiv ca sa obtin 100.

[•PlayLikeNeverB4]

Vezi ca si coada ti-e declarata nmax si, cum un nod poate intra de mai multe ori, exista sanse sa depaseasca acea valoare.

[•BalcauIonut]

Dumnezeule...am stat o ora chinuinduma sa vad unde am gresit ca sa-mi dau seama ca scrisasem "Ciclu Negativ!" cu N mare
Imi vine sa sparg ceva!

[•algotroll]

Bellman-Ford cu coada cu prioritate chiar are complexitatea mai mare (O(N*M*log2N)) decat cu coada simpla? (O(N*M)) cf. textului

[•laurion]

Bellman-Ford cu coada cu prioritate chiar are complexitatea mai mare (O(N*M*log2N)) decat cu coada simpla? (O(N*M)) cf. textului

Da, coada de prioritate este un heap, si operatiile au complexitatea O(lg N) pe cand coada simpla este un vector si ai complexitate O(1). Vezi Algoritmul lui Dijkstra din Arhiva Educationala.

[•danalex97]

Am o intrebare , anume de ce cu coada ( queue ) iau 100 si cu un vector care simuleaza o coada ( vector din STL ) iau doar 35 ?