Posted By: Ped (PhoneChange see Query) on 'CZprogram'
Title:     Re: Hledam...
Date:      Wed Aug  6 15:56:30 1997


 Ono nechcem byt provokater, ale plne suhlasim s Marwinom. Popisali ste 
dost postov o nicom, pretoze pri algoritmizacii problemu Vam akosi MUSI 
vyjst, ze 2D 3D reprezentacia sa v pocitaci zleje do jedneho grafu a je 
to teda uplne jedno. (Paja, hlavne u Teba ma to zarazilo :)

 Inac, co sa tyka samotneho algoritmu, tak ja osobne pouzivam taketo 
nieco (velmi by ma zaujimalo, keby niekto nastudoval toho Dij... a 
povedal mi, ako to funguje):

 Mas vychodzi bod s hodnotou nula, a zvysne body s max. hodnotou na 
zaciatku. Plus zoznam hran pre kazdy bod.
 Vyjdem z pocitaocneho bodu: 
  pre vsetky jeho hrany
   Temp_hodnota = hodnota_poc_bodu + dlzka_hrany
   ak Temp_hodnota < hodnota_ciel_bodu tak
     hodnota_ciel_bodu = Temp..
     Pridaj cielovy bod do zasobnika bodov, ktore sa budu tymto
     sposobom skumat.
   inak nic.
 ukonci skumanie bodu -> zober zo zasobnika dalsi, az kym nie je prazdny 
 zasobnik.

 Ked som to skusal na 2D sieti v pascale, tak to islo dost rychlo a pocet 
skumani bodov sa drzal okolo 2.5 * n * n, cize casova zlozitost bola 
O(N^2) aj ked je to brute_force algoritmus.
 To bolo sice pravidelna siet bodov n*n pospajanych so susedmi, ale to je 
vlastne to iste, ako mas ty.

 Joj, este co vlastne tym algoritmom dostanes:
Pre kazdy bod hodnota = max -> neexistuje cesta z pociatku
                       cislo = dlzka najkratsej cesty.
Samotnu cestu zrekonstruujes spatnym chodom. Hladas hranu z cieloveho 
bodu, ktora po odpocitani od hodnoty da hodnotu toho bodu na opacnom 
konci hrany.

Your Mr.PED / 7 GODS demo group member. ALWAYS served COOL ! *keep smiling*
   (_
  "~/~"      -=- deRATized RAT -=-    QUERY/FINGER hellco@kosice.upjs.sk
  ,_oo_,   From 1.March is phone to Slovakia +421 ! Poor M$ Wind0zE uzerz...
    `'        NEW: 7 GODS demo group WWW pages: "http://music.box.sk/7gods/"