Az oldal tölt...

Keresés

Legújabb cikkek

Támogató

Fazekas

Szabványok

Valid XHTML 1.0 Strict

Valid CSS!

Szerkesztő
Kategória: Megoldás - Feladat Évfolyam: 9.
Kulcsszó: Összefüggő gráfok Lektorálás: Nem lektorált

A minimális költségű út problémája

Megoldás

Kiválasztunk a legkisebb élek közül egyet. Innen arra megyek tovább, amerre a legkisebb él mutat, ha ott még nem voltunk.
Növekvő sorrendbe rendezem az éleket. Mindig kiválasztom a soron következő legkisebbet, kivéve ha ez kört zár be.
A mohó algoritmussal létrehozunk egy feszítőfát. Ha nem húztuk be a legkisebb élt, akkor tegyük meg! Így létrejön egy kör, mert összefüggő volt a gráf. Ha ebből a körből elhagyunk egy másik élt, akkor az összeg biztosan csökken. Így a legkisebb él biztos benne van a keresett feszítőfában, hasonlóan a második, harmadik stb. legkisebb is.

Az algoritmusok

A mohó algoritmus helyes alkalmazásának bizonyítása

I.

II.

A feladatot két algoritmussal is megoldhatjuk.
Főgombok VisszaElőreFrissítHibát találtál? Jelentsd!NyomtatMutat