Ооба, туура айтасыз Примдин алгоритми дижкстранын алгоритминдей иштейт, бирок Примдин алгоритминде терс четтери бар iден jге чейинки эң кыска жолду эсептебеши керек. Демек, алардын дагы бир алгоритми, алардын б.а. Беллман-Форддун iден jге чейинки эң кыска жолду терс чети менен эсептөө үчүн алгоритми.
Примдин алгоритми эмне үчүн иштейт?
Информатикада Примдин алгоритми (Жарниктин алгоритми катары да белгилүү) салмактуу багытталбаган график үчүн минималдуу даракты таба турган ач көз алгоритм Бул анын төмөнкү топтомун табат дегенди билдирет ар бир чокусун камтыган даракты түзгөн четтер, мында дарактын бардык четтеринин жалпы салмагы минималдаштырылган.
Примдин алгоритми туурабы?
Тууралыктын далили
Примдин алгоритминин туура экенин алгоритм тарабынан курулган өсүп жаткан дарактагы индукция менен далилдейбиз. … Биз Ti минималдуу узундуктагы дарактын бир бөлүгү экенин кыскартуу аркылуу далилдейбиз. ei=(v, u) Прим алгоритми тарабынан табылган чети болсун жана ал минималдуу жайылган дарактын чети эмес деп ойлойлу.
Примдин алгоритми канчалык эффективдүү?
Примдин алгоритми эффективдүү иштейт эгер биз чокуну туташтырган эң арзан салмактардын d[v] тизмесин сактасак, даракта жок v, кандайдыр бир чокуга мурунтан эле даракта. …
Prims терс салмактар менен иштейби?
Примдикиби? Чечим: Ооба, эки алгоритм тең терс жээк салмактары менен иштейт, анткени кесүү касиети дагы эле колдонулат.
