Ja, je hebt gelijk Het algoritme van Prim werkt als het algoritme van dijkstra, maar in het algoritme van prim zou het niet de kortste weg van i naar j met negatieve randen moeten berekenen. Dus er is een ander algoritme, namelijk hun Bellman-Ford-algoritme voor het berekenen van het kortste pad van i naar j met een negatieve rand.
Waarom werkt het algoritme van Prim?
In de informatica is het algoritme van Prim (ook bekend als het algoritme van Jarník) een hebzuchtig algoritme dat een minimale opspannende boom vindt voor een gewogen ongerichte graaf Dit betekent dat het een subset vindt van de randen die een boom vormen die elk hoekpunt omvat, waarbij het totale gewicht van alle randen in de boom wordt geminimaliseerd.
Is het algoritme van Prim correct?
Bewijs van juistheid
We bewijzen dat Prim's algoritme correct is door inductie op de groeiende boom die door het algoritme is geconstrueerd. … We bewijzen door samentrekking dat Ti deel uitmaakt van een minimaal opspannende boom. Laat ei=(v, u) de rand zijn die wordt gevonden door het algoritme van Prim en neem aan dat het geen rand is van een minimaal opspannende boom.
Hoe efficiënt is het algoritme van Prim?
Prim's algoritme werkt efficiënt als we een lijst d[v] bijhouden van de goedkoopste gewichten die een vertex, v, die niet in de boom staat, verbinden met een al vertex in de boom. …
Werken Prims met negatieve gewichten?
Is dat van Prim? Oplossing: Ja, beide algoritmen werken met negatieve randgewichten omdat de snij-eigenschap nog steeds van toepassing is.
