Hálozatépítés probléma
Egy új légitársaság az alábbi útvonalakra tudja megszerezni a járat indítási engedélyt. A célunk, hogy olyan hálózatot hozzanak létre, amelyben mindenhová el lehet jutni átszállásokkal. A cél minél kevesebb kilométerrel megoldani az összes város összeköttetését.
ÚtvonalTávolság (100km)
Paris-Berlin 8
Paris-Brussels 4
Paris-Milan 6
Berlin-Prague 2
Brussels-Prague 7
Milan-Rome 4
Prague-Budapest 4
Rome-Budapest 4
Brussels-Rome 11
Prague-Milan 6