Այո, դուք իրավացի եք Prim-ի ալգորիթմն աշխատում է ինչպես dijkstra-ի ալգորիթմը, սակայն prim-ի ալգորիթմում այն չպետք է հաշվարկի i-ից մինչև j ամենակարճ ճանապարհը՝ ունենալով բացասական եզրեր: Այսպիսով, նրանց մեկ այլ ալգորիթմ է, օրինակ՝ Բելման-Ֆորդի ալգորիթմը՝ բացասական եզրով i-ից մինչև j ամենակարճ ճանապարհը հաշվարկելու համար::
Ինչու է աշխատում Պրիմի ալգորիթմը:
Համակարգչային գիտության մեջ Պրիմի ալգորիթմը (նաև հայտնի է որպես Յարնիկի ալգորիթմ) ագահ ալգորիթմ է, որը գտնում է նվազագույն ընդգրկող ծառ կշռված չուղղորդված գրաֆիկի համար Սա նշանակում է, որ այն գտնում է ենթաբազմություն եզրեր, որոնք կազմում են ծառ, որը ներառում է յուրաքանչյուր գագաթ, որտեղ ծառի բոլոր եզրերի ընդհանուր քաշը նվազագույնի է հասցվում:
Ճի՞շտ է Պրիմի ալգորիթմը:
Ճշտության ապացույց
Մենք ապացուցում ենք, որ Պրիմի ալգորիթմը ճիշտ է ինդուկցիայի միջոցով ալգորիթմի կողմից կառուցված աճող ծառի վրա: … Մենք կծկումով ապացուցում ենք, որ Ti-ը նվազագույն տարածվող ծառի մասն է: Թող ei=(v, u) լինի Պրիմի ալգորիթմի կողմից հայտնաբերված եզրը և ենթադրենք, որ այն նվազագույն ընդգրկող ծառի եզր չէ:
Որքանո՞վ է արդյունավետ Prim-ի ալգորիթմը:
Prim-ի ալգորիթմն արդյունավետ է աշխատում եթե մենք պահենք ամենաէժան կշիռների ցանկը d[v], որոնք կապում են գագաթը, v, որը ծառի մեջ չէ, արդեն որևէ գագաթի հետ: ծառի մեջ. …
Արդյո՞ք Prims-ն աշխատում է բացասական կշիռներով:
Արդյո՞ք Prim's-ը: Լուծում. Այո, երկու ալգորիթմներն էլ աշխատում են բացասական եզրերի կշիռներով, քանի որ կտրվածքի հատկությունը դեռ գործում է:
