matematikk.net

Hei ,
Er det noen som kan hjelpe meg å forstå hvordan man bruker en Kurskals algoritme for å finne kortest vei i en graf og hva er egentlig forskjellen mellom Kurskals og Prims algoritme ?

takk på forhånd

Disse algoritmene brukes vel til å finne minimale spenntrær.

Prims algoritme er grådig, du velger ut en tilfeldig node og velger alltid den kanten ut fra noden med minst kostnad.

Med Kruskals algoritme sorterer du alle kantene etter kostnad og ser på dem i stigende rekkefølge. Ta med en kant i spenntreet så lenge kanten ikke lager en sykel. Fortsett til du ikke kan legge til flere kanter.