94
94
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.