Hoy en dia tenemos muchisimas herramientas capaces de calcularnos las rutas mas cortas entre varios puntos ¿como es eso posible?... ¡Gracias al algoritmo de Prim!
"Supóngase N = {1, 2, 3,…,n}. El algoritmo de Prim comienza con
un conjunto U inicializado con cualquier nodo, por ejemplo {1}. Luego se hace
crecer un árbol generador, arco por arco. En cada paso se encuentra el arco más
corto (u, v) que conecta a U y N – U y luego se adiciona v, el nodo en N – U, a
U. Se repite este paso hasta que U = N
El algoritmo es resumido en los siguientes pasos:
Algoritmo de PRIM.
Paso 0. Iniciar el grafo T con un solo nodo i escogido al azar: N
= {i}, A = 0, T = ({i},0)
Paso 1. Seleccionar el arco (i, j) cuya longitud es la menor entre
todos aquellos arcos adyacentes a T. Adicionar este arco (i,j) a T y j al
conjunto de nodos de T
Paso 2. Preguntar si T ya es un árbol que contiene todos los nodos
de G y detenerse. En este caso contrario repetir el paso 1.
CONCLUSIÓN
El algoritmo de PRIM es un método para poder hallar un árbol recubridor mínimo en
un grafo acíclico conexo no dirigido que nos permita hallar en un grafo el
coste mínimo para una serie de actividades.
Este algoritmo se usa normalmente para ahorrar recursos, su aplicación mas común es
la implementación de cables de redes,
de servidores, de postes de luz entre otros.
Es decir el Algoritmo de Prim sirve para poder hallar el
"árbol recubridor mínimo", en un grafo conexo no dirigido.
Ejemplos
Aplicando el algoritmo de Prim en un problema de la vida real:
Situación: Implementación del cableado para el servicio de televisión por cable en ciertos
puntos de un sector de la ciudad de Puno (Perú).
Problema: Ahorrar la mayor cantidad de cable (recursos) en los
puntos estratégicos (torres de distribución)
para llegar a todos los destinos deseados.
Datos: Distancia entre torres y casas es de 10 metros (cada casa)
Planteamiento: En el figura 1 se observa la ubicación de las
torres de distribución y las viviendas.
En la figura 2 transformamos el conjunto de torres y viviendas en
un Grafo.
Figura 2
En la figura 3 Aplicamos el Algoritmo de Prim en el grafo para
hallar el árbol recubrir mínimo o en otras palabras la ruta optima para ahorra
la distancia del cableado.
Figura 3
