Въпрос за Advanced Graph Algorithms - Cable Network - Софтуерен университет

Въпрос за Advanced Graph Algorithms - Cable Network

Първата задача от домашното е това. В условието има хинт: Modify Prims's algorithm. Until the budget is spent, connect the smallest possible edge from connected node to non-connected node. Ако не бъркам идеята на Прим ще вземем първия връх (0) и в приоритетна опашка или подереден сет ще вземе всички ребра, който излизат от него - в този случай 0-4{6} , 0-8{5}, 0-3{9}, 0-5{4}. Оттук следва, че първото избрано ребро ще е 0-5 с тежест 4 и т.к 5 не е все още част от мрежата, можем да го добавим. Откъдето пък реброто 5-3 се обезсмисля да бъде част от мрежата. И крайното решение, което получавам, започва да се различава от даденото като пример. Та какво пропускам при решението на тази задача с алгоритъма на Прим ?? Вече я реших с модифициран Крускъл, но там пък последния тест гърми в Judge..

Идеята на задачата е че започваш с някаква изградена мрежа и искаш да я разшириш да включва колкото можеш нови върхове в графа в рамките на някакъв бюджет. Не се подлъгвай че трябва да почваш от точка 0. Ако си интернет доставчик и имаш кабели до 3 блока и някой човек от 4ти блок каже че иска интернет, няма да дръпнеш кабел до него от 1вия блок който си окабелил, а ще дръпнеш кабел от най близкият окабелен блок (който и да е той). Като погледнеш примера и видиш че елементи {0, 4, 8, 3, 12} вече са свързани, разглеждайки 5 ще видиш че можеш да свържеш 5 и от точка 0 и от точка 3 (и 2те точки са в началната мрежа с която започваме). Разглеждайки връзките се вижда че е по лесно да го свържеш от точка 3 {3->5 = 2} отколкото от 0 {0->5 = 4}.