Algoritmo de Minieka
De Wikipedia, la enciclopedia libre
El Algoritmo de Minieka es el denominado centro absoluto en un grafo general. El procedimiento consiste en determinar la mejor localización posible en cada arista (i,j) la cual se encuentra en el centro local con respecto a un punto n al que se accede óptimamente a través de i y al punto v que es el más alejado de j de los que están más lejos de i que n. El punto recorre los puntos de demanda ordenados de acuerdo a su distancia a i desde el más lejano al más próximo. Al pasar de n al siguiente, si la distancia del primero supera la distancia de v a j, v toma su valor. Para cada par de punto u y v, el correspondiente centro local tiene por radio:
- R = ½(d(u,i) + e(i,j) + d(v,j))
Estará en el interior de (i,j) si:
- d(u,i) < t < d(u,i) + e(i,j)
- d(v,j) < t < d(v,j) + e(i,j)
X € (s,t) es un centro local respecto a los vértices i u j sí y solo sí:
- d(i,x) = d(j,x) (distancia de i a x pasando por s (= distancia de j a x pasando por t ).
- d(i,x) = dis + lsx = lxt + dtj = d(s,x)
