Ja, du har ret Prims algoritme fungerer som dijkstras algoritme, men i prims algoritme bør den ikke beregne den korteste vej fra i til j med negative kanter. Så deres er en anden algoritme er deres dvs. Bellman-Ford algoritme til at beregne korteste vej fra i til j med negativ kant.
Hvorfor virker Prims algoritme?
I datalogi er Prims algoritme (også kendt som Jarníks algoritme) en grådig algoritme, der finder et minimumsspændingstræ for en vægtet urettet graf Dette betyder, at den finder en delmængde af kanterne, der danner et træ, der omfatter hvert hjørne, hvor den samlede vægt af alle kanterne i træet er minimeret.
Er Prims algoritme korrekt?
Bevis for rigtighed
Vi beviser, at Prims algoritme er korrekt ved induktion på det voksende træ, der er konstrueret af algoritmen. … Vi beviser ved sammentrækning, at Ti er en del af et minim alt spændingstræ. Lad ei=(v, u) være kanten fundet af Prims algoritme, og antag, at det ikke er en kant af et minimumspændende træ.
Hvor effektiv er Prims algoritme?
Prims algoritme fungerer effektivt hvis vi fører en liste d[v] over de billigste vægte, som forbinder et toppunkt, v, som ikke er i træet, til et hvilket som helst toppunkt i forvejen i træet. …
Fungerer Prims med negative vægte?
Er Prim's? Løsning: Yes, begge algoritmer fungerer med negative kantvægte, fordi cut-egenskaben stadig gælder.
