Taip, tu esi teisus Prim algoritmas veikia kaip dijkstra algoritmas, bet prim algoritme jis neturėtų skaičiuoti trumpiausio kelio nuo i iki j su neigiamomis briaunomis. Taigi, jų yra kitas algoritmas, ty Bellman-Ford algoritmas, skirtas apskaičiuoti trumpiausią kelią nuo i iki j su neigiama briauna.
Kodėl veikia Prim algoritmas?
Kompiuterių moksle Primo algoritmas (taip pat žinomas kaip Jarník algoritmas) yra godus algoritmas, kuris suranda minimalų apimantį medį svertiniam nenukreiptam grafikui Tai reiškia, kad jis suranda poaibį briaunos, sudarančios medį, apimantį visas viršūnes, kur bendras visų medžio briaunų svoris yra sumažintas.
Ar Prim algoritmas teisingas?
Teisingumo įrodymas
Mes įrodome, kad Primo algoritmas teisinga indukcija augančiame medyje, sukonstruotame pagal algoritmą. … Sutraukimu įrodome, kad Ti yra minimalaus besitęsiančio medžio dalis. Tegu ei=(v, u) yra briauna, kurią randa Primo algoritmas, ir manykime, kad tai nėra minimalaus apimančio medžio briauna.
Ar efektyvus yra Prim algoritmas?
Prim algoritmas veikia efektyviai jei saugosime sąrašą d[v] pigiausių svorių, jungiančių viršūnę v, kurios nėra medyje, su bet kuria jau viršūne medyje. …
Ar Prims veikia su neigiamais svoriais?
Ar Prim's? Sprendimas: Taip, abu algoritmai veikia su neigiamu briaunų svoriu, nes vis tiek galioja pjūvio savybė.
