GN-cel mai mare cost minim

[•flaviumanica]

Hello! Am si eu o intrebare la urmatoarea problema: Se citesc date despre un graf neorientat ponderat. Care e cel mai lung drum minim ce pleaca din nodul 1 si prin ce noduri trece?
Am citit matricea,am facut matricea drumurilor de cost minim. Apoi,am reusit sa afisez cel mai lung drum,insa folosind parcurgerea in adancime. Am nevoie,insa,de o modalitate sa rezolv problema in totalitate cu matricea costurilor minime. Multumesc!

[•costi_.-.]

So cel mai mare cost minim e maximul din linia 1. Apoi, poti folosi tehnica DeI :

Cod:

void descompune(int x,int y)
{
  int stop=0, k=1;
  while(!stop && k<N)
 {
    if((A[x][k]+A[k][y] == A[x][y])&&(x!=k && y!=k))
     {
       descompune(x,k);
       descompune(k,y);
       stop=1;
      }
    k++;
}

if(stop)
 prelucreaza k;
}

Apelezi descompune(1, nodul_cu_pricina)   ;

[•flaviumanica]

So cel mai mare cost minim e maximul din linia 1. Apoi, poti folosi tehnica DeI :

Cod:

void descompune(int x,int y)
{
  int stop=0, k=1;
  while(!stop && k<N)
 {
    if((A[x][k]+A[k][y] == A[x][y])&&(x!=k && y!=k))
     {
       descompune(x,k);
       descompune(k,y);
       stop=1;
      }
    k++;
}

if(stop)
 prelucreaza k;
}

Apelezi descompune(1, nodul_cu_pricina)   ;

Multumesc mult,am reusit sa o fac asa.
Dar la sfarsit de fapt se prelucreaza y,nu k ...

[•costi_.-.]

Asa e, cred ca m-am grabit cand am scris.
In fine, ma bucur ca ti-a fost de folos.