New telephone lines must be installed to connect 9 cities (A, B, C, D, E, F, G, H and J). Due to government regulations, the only possible connections that are allowed are
shown by
the edges on the graph below. The numbers on the edges indicate the cost (in millions of
dollars)
of each possible connection.
The telephone company wishes to connect the cities in the cheapest possible way.
5
000
5
5
LL
2
3
3
3
E
00
2
5
ICO
7
The total cost of the optimal solution to this problem is: