Algoritmus
Az első kérdésre egyszerűen a minimális összsúlyú feszítőfa súlyát kell megadni, ez például Kruskal algoritmusával meghatározható.
A második legolcsóbb hálózat megkapható $n-1$ újabb "MST" futtatásával:
hagyjuk el a lehetséges összekötések gráfjából egyesével az optimális fa éleit, és minden egyes elhagyáskor futassuk le az "MST" algoritmust a maradék gráfra. A kapott összsúlyok közül a legkisebb adja meg a második kérdésre a választ.
Kódok
