Algoritmo De Prim

ARBOL DE MINIMA EXPANSION


El programa de PRIM Y BÚSQUEDA EXHAUSTIVA DE ÁRBOL DE MÍNIMA EXPANSIÓN que
realice fue elaborado en el lenguaje de programación Python, con el editor de textoSublime Text.
Descripcion del problema: Establecer una red de comunicaciones entre las ciudades de Cancún,
Mérida, D.F., Guadalajara, Monterrey y Tijuana. Para optimizar recursos, la red debeseleccionar
las conexiones de menor longitud total entre todas las ciudades

¿Cómo se resolvió el problema?
CREACIÓN DEL GRAFO
Para crear el grafo me apoye de Google Maps, para encontrar las distanciasentre cada
pareja de ciudades, Google Maps no da dos rutas distintas entre las ciudades, solo tome
en cuenta la ruta con la distancia menor ignorando también las rutas en avion. Como
Resultado medio la Siguiente Tabla
Ciudad A
Cancún
Cancún
Cancún
Cancún
Cancún
Mérida
Mérida
Mérida
Mérida
Distrito Federal
Distrito Federal
Distrito Federal
Monterrey
Tijuana
Guadalajara

CiudadB
Mérida
Distrito Federal
Guadalajara
Monterrey
Tijuana
Distrito Federal
Guadalajara
Monterrey
Tijuana
Guadalajara
Monterrey
Tijuana
Tijuana
Guadalajara
Monterrey

Distancia
Menor(Km)
306
1,617
2,149
2,325
4,372
1,315
1,847
2,022
4,069
537
1,069
2759
2,244
2226
769

Y el grafo de esta combinación de ciudades es el siguiente

CANCUN

MERIDA

306

1,3154,069
TIJUANA

MONTERREY
2,244

2,759
769

GUADALAJARA

D.F.
537

ALGORITMO DE PRIM
El algoritmo de PRIM primero lo resolví de forma manual, y después lo programe para
analizar losresultados.

FORMA MANUAL
FORMATO: (PADRE) CIUDAD (PESO)

S= (Cancún) Mérida (306),

(Mérida) DF (1315), (DF) Guadalajara (537),
(Guadalajara) Monterrey (769),
(Guadalajara) Tijuana (2226).A= { (Cancún) Mérida (306),

(Cancún) Tijuana (4372),
(Cancún) DF (1617),
(Cancún) Guadalajara (2149),
(Cancún) Monterrey (2325),
(Mérida) Tijuana
(4069),
(Mérida) DF (1315),
(Mérida)...