MathCastle
Graph TheoryChallengeGraph Algorithms

Graph Algorithms · Challenge problem

A town's possible roads among intersections AA–FF are AB:3,AC:6,BC:2,BD:5,CD:4,CE:7,DE:3,DF:8,EF:2AB{:}3, AC{:}6, BC{:}2, BD{:}5, CD{:}4, CE{:}7, DE{:}3, DF{:}8, EF{:}2. The town wants road CECE built no matter what, in addition to connecting every intersection as cheaply as possible otherwise. What is the minimum total cost of a road network that includes CECE?