Árbol de expansión: Participación 1

Árbol de Expansión

Las distancias en millas entre ciudades de Indiana: Gary, Fort Wayne, Evansville, Terre Haute y South Bend, se muestran en la siguiente tabla. Es necesario construir un sistema estatal de carreteras que una todas estas ciudades. Suponga que por razones políticas no es necesario construir una carretera a Gary y Fort Evansville ¿Cuál es la longitud mínima de la carretera requerida?

	Gary	Fort Wayne	Evansville	Terre Haute	South Bend
Gary	--	132	217	164	58
Fort Wayne	132	--	290	201	79
Evansville	217	290	--	113	303
Terre Haute	164	201	113	--	196
South Bend	58	79	303	196	--

Arco	Peso	Entra a la red
Ga a S	58	SI
F a S	79	SI
E a T	113	SI
Ga a F	132
Ga a T	164	SI
T a S	196
F a T	201
Ga a E	217
F a E	290
E a S	303

Solución:
La longitud mínima es de 414.