El algoritmo de Prim, como hallar la ruta optima.

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.

Aplicación del Algoritmo de Prim

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

Fuente y mas información aquí.