Da, u pravu ste Primov algoritam radi kao Dijkstrin algoritam, ali u Primovom algoritmu ne bi trebao izračunati najkraći put od i do j koji ima negativne rubove. Dakle, njihov je drugi algoritam njihov tj. Bellman-Ford algoritam za izračunavanje najkraćeg puta od i do j s negativnim rubom.
Zašto Primov algoritam radi?
U informatici, Primov algoritam (također poznat kao Jarníkov algoritam) je pohlepni algoritam koji pronalazi minimalno razapinjuće stablo za ponderirani neusmjereni graf To znači da pronalazi podskup rubovi koji tvore stablo koje uključuje svaki vrh, pri čemu je ukupna težina svih bridova u stablu minimizirana.
Je li Primov algoritam točan?
Dokaz ispravnosti
Dokazujemo da je Primov algoritam točan indukcijom na rastućem stablu konstruiranom algoritmom. … Dokazujemo kontrakcijom da je Ti dio minimalnog razapinjućeg stabla. Neka je ei=(v, u) rub pronađen Primovim algoritmom i pretpostavimo da to nije rub minimalnog razapinjućeg stabla.
Koliko je učinkovit Primov algoritam?
Primov algoritam radi učinkovito ako vodimo popis d[v] najjeftinijih težina koje povezuju vrh, v, koji nije u stablu, s bilo kojim vrhom već u stablu. …
Radi li Prims s negativnim utezima?
Da li Prim's? Rješenje: Da, oba algoritma rade s negativnim težinama ruba jer svojstvo rezanja i dalje vrijedi.
