Studoši

Jel netko može objasniti 5. korak u Bondy-chvatal auditornima zašto je uzet sad DC za pq kad im se ne križaju up i pq nije mi jasno objašnjenje profesoru u pdf-u

MrPeanutButter da ni meni nije jasno. Jer po njihovim uputama iz preza bi mi smjeli za pq uzet brid BC, no ono što se zapravo dogodi kad uzmeš BC za pq je da dobiješ odvojeni trokut BFG, odnosno dobiješ nepovezan graf, tako da ili ja nešto ne kužim ili je algoritam sa preza nepotpun.

je ovo greška na auditornim za put A-D za WFI ?
zasto krene sa Pi[1,5] kada je d 4?

Asdf Da mislim da je greska

Ako u Dijakstri imamo situaciju da smo neki čvor već obišli, ali nakon tog dođemo do nekog puta koji je kraći/jeftiniji do tog već posjećenog čvora - je li ažuriramo ili ga uopće ne posječujemo jer smo ga već posjetili?
Eo primjer sa 2.1 videa - ako cijenu D->C stavimo da je npr -1 onda će se dogoditi da smo C već obišli, ali kad smo došli do D smo skužili da je preko njega jeftinije doći do tog C-a. Što u tom slučaju?

anon00 Mislim da u tom slučaju ne obilaziš ponovno isti nego samo updateaš vrijdnost

anon00 Ako sam ja dobro skužio, ažuriramo samo udaljenosti neposjećenih čvorova. Tako mi se čini iz ovog pseudokoda koji su stavili na prezentaciju:

Vidiš da se provjerava postoji li kraći put samo do onih vrhova koji su u work - dakle onih koje još nismo obišli. To se također podudara sa postupkom koji sam našao ovdje , gdje eksciplitno kaže da ne updatamo udaljenosti vrhova koje smo još posjetili.

Također, mislim da Dijkstra ne može raditi sa negativnim težinama, tako da bi to također moglo uzrokovati neka čudna rješenja.

indythedog Hvala puno!
Najviše me zbunilo što je prof u videu uzeo C u obzir i rekao necemo ga updateati jer je 4 veći od 3 kojeg vec imamo za taj C.

Svojstvo Dijkstre je da nikad ni ne mozes naci kraci put do cvora ako si ga vec posjetio, tj. u trenutku kad posjecujes neki cvor znas da je za njega vec izracunat konacni najkraci put (pod uvjetom da nema negativnih tezina, Dijkstra ne radi s negativnim tezinama).

ima negdje malo detaljniji tutorial za bondy chvatal? nista mi nije jasno ni iz preze ni iz onog pdfa

Mozemo li raditi Dijkstra MST nad grafom s negativnim tezinama? I jel ulazi transformacija tezina u ispit?

Jel se ovakvi zadaci gdje imamo neusmjeren graf isto rješavaju Bellman-Fordom? Ako da, jel onda npr. brid AB brojim 2x, tj. AB i BA, ili samo jednom?

indythedog Mislim da bi ovdje isla Dijkstra, nema negativnih vrijednosti, a manje je slozenosti od BF.

indythedog Piše najučinkovitijim, tak da je to Dijkstra, al ak oces za vijezbu rijesit BF-om, najlakse je da pretvoris u usmjereni tako da poduplaš sve bridove (odnosno napraviš ovo kaj si reko)

ima li ko rjesenja starih ispita?

Jel ima još koji tip zadatka/gradivo osim kineskog poštara/trgovačkog putnika koje mogu zadati bez da specificiraju algoritam pa da moramo znati koji algoritam je potreban?

Maddy Mislim da bi ipak isao BF posto se trazi od čvora F do svih ostalih. Dijkstra je za udaljenost između dva određena čvora.

niknik Dijkstra je za udaljenost izmedu izvora i svih ostalih vrhova. Ne znam odkud zabluda u prezentacijama da je Dijkstra za udaljenost izmedu dva vrha

[obrisani korisnik] Da, ocigledno je da se moze iscitati i udaljenost nekog vrha do ostalih vrhova, ali ne znam kak onda razlikovati kad koristiti Dijkstru, a kad BF ako u zadatku ne piše. Osim ako se vidi da ima negativnih bridova pa je jasno.

sta je najlakse za naucit od preostalih stvari?

NISAM ASISTENT minimalna razapinjujuća stabla, zatim problem trgovačkog putnika
i skip liste su izi ak formulu zapamtiš

NISAM ASISTENT rekao bih da su skip liste i 01knapsack FPTAS najteži tu