Imprimă pagina - GN-cel mai mare cost minim

Titlul: GN-cel mai mare cost minim
Scris de: Flaviu Manica din Ianuarie 28, 2013, 17:08:51

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!

Titlul: RÄƒspuns: GN-cel mai mare cost minim
Scris de: Costinnel din Ianuarie 28, 2013, 17:24:42

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) :) ;

Titlul: RÄƒspuns: GN-cel mai mare cost minim
Scris de: Flaviu Manica din Ianuarie 29, 2013, 16:05:36

Citat din mesajul lui: Costinnel din Ianuarie 28, 2013, 17:24:42

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 ...

Titlul: RÄƒspuns: GN-cel mai mare cost minim
Scris de: Costinnel din Ianuarie 29, 2013, 16:24:01

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Flaviu Manica din Ianuarie 28, 2013, 17:08:51