AlGORITMO DE PRIM

AlGORITMO DE PRIM

Robert Prim en 1957 descubrió un algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST). 

Este problema es un problema típico de optimizacion combinatoria, que fue considerado originalmente por Otakar Boruvka en 1926 mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia. Este problema también fue resuelto por Joseph B. Kruskal en 1956.

El algoritmo de Prim encuentra un árbol de peso total mínimo conectando nodos o vértices con arcos de peso mínimo del grafo sin formar ciclos.

algoritmo de Prim (árbol de coste total mínimo)

Consiste en dividir los nodos de un grafo en dos conjuntos: procesados y no procesados. 

Al principio, hay un nodo en el conjunto procesado que corresponde a el equipo central; en cada interacción se incrementa el grafo de procesados en un nodo (cuyo arco de conexión es mínimo) hasta llegar a establecer la conexión de todos los nodos del grafo a procesar. A continuación se muestra el pseudocódigo del algoritmo:

Prim ( L [1..n , 1..n ]) : 'conjunto de arcos

'Inicialización: sólo el nodo 1 se encuentra en B

T =NULL 'T contendrá los arcos del árbol de extensión mínima Distmin[1]=-1

para i=2 hasta n hacer

    más_próximo [ i ]=1

    distmin [ i ]=L [ i , 1]

para i=1 hasta n -1 hacer

    min=infinito

            para j=2 hasta n hacer

                    si 0 <= distmin [ j ] < min entonces

                    min=distmin [ j ]

                    k=j

             T=T union {{mas_próximo [ k ], k }}

             distmin [ k ]= -1 'se añade k a B

            para j=2 hasta n hacer

                     si L [ j , k ] < distmin [ j ] entonces

                    distmin [ j ]=L [ j , k ]

                    más_próximo [ j ]=k

devolver T