Camino mínimo

Se denomina camino mínimo entre dos vértices V y W, al camino óptimo entre ambos vértices. Para determinar el camino mínimo entre dos vértices se utiliza el siguiente algoritmo:

desde i=1 hasta número_vértices haz
        desde j=1 hasta número_vértices haz
                si w[i,j]=0 entonces
                        q[[i,j]<--infinito
                en caso contrario
                        q[i,j]<--w[i,j]
desde k=1 hasta número_vértices haz
        desde i=1 hasta número_vértices haz
                desde j=1 hasta número_vértices haz
                        q[i,j]<--min(q[i,j], q[i,k] + q[k,j])

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz

Publicado en Estructura de datos

Suscríbete:

who's online