Bəli, haqlısan Primin alqoritmi Dijkstra alqoritmi kimi işləyir, lakin primin alqoritmində mənfi kənarları olan i-dən j-ə qədər ən qısa yolu hesablamamalıdır. Beləliklə, onların başqa bir alqoritmi mənfi kənar ilə i-dən j-ə qədər ən qısa yolu hesablamaq üçün Bellman-Ford alqoritmidir.
Prim alqoritmi niyə işləyir?
Kompüter elmində Prim alqoritmi (həmçinin Jarník alqoritmi kimi tanınır) çəkili istiqamətləndirilməmiş qrafik üçün minimum yayılma ağacı tapan acgöz alqoritmdir Bu o deməkdir ki, o, alt çoxluq tapır ağacdakı bütün kənarların ümumi çəkisinin minimuma endirildiyi hər təpənin daxil olduğu ağacı meydana gətirən kənarlar.
Prim alqoritmi düzgündür?
Düzgünlük sübutu
Biz Primin alqoritminin induksiya ilə düzgün olduğunu alqoritm tərəfindən qurulan böyüyən ağac üzərində sübut edirik. … Biz daralma ilə sübut edirik ki, Ti minimal yayılan ağacın bir hissəsidir. ei=(v, u) Prim alqoritmi tərəfindən tapılan kənar olsun və onun minimum yayılan ağacın kənarı olmadığını fərz edək.
Prim alqoritmi nə qədər səmərəlidir?
Prim alqoritmi səmərəli işləyir təpə nöqtəsini birləşdirən ən ucuz çəkilərin d[v] siyahısını tutsaq, ağacda olmayan v, artıq hər hansı təpəyə ağacda. …
Prims mənfi çəkilərlə işləyirmi?
Prim varmı? Həll yolu: Bəli, hər iki alqoritm mənfi kənar çəkilərlə işləyir, çünki kəsmə xüsusiyyəti hələ də tətbiq olunur.
