Algoritmo matricial de shumbel

Solo disponible en BuenasTareas
  • Páginas : 3 (668 palabras )
  • Descarga(s) : 4
  • Publicado : 9 de junio de 2010
Leer documento completo
Vista previa del texto
ALGORITMO MATRICIAL DE SHUMBEL

Este algoritmo propuesto por Shumbel en Structure in Communication Net, Symposium of Information Networks en 1954, establece un procedimiento para hallar latrayectoria de valor máximo o valor mínimo, usando productos de matrices a partir de la matriz inicial de costos o adyacencia.

ALGORITMO DE SHUMBEL

Sea M la matriz de valores asociados a un grafo G, lacual se representa por [pic] donde los elementos [pic] se definen de dos formas:

a. Si se desea encontrar la matriz de valor mínimo, se establece:

[pic]

b. Si se desea encontrar latrayectoria de valor máximo, se define:

[pic]

La matriz de trayectorias de valor óptimo es [pic] en donde n es el número de nodos en el grafo.

Si en un momento dado se obtiene [pic]= [pic], siendo m< n – 1 la matriz [pic] es la matriz de trayectorias de valor optimo, o sea que la matriz de valor optimo se obtiene del calculo de las siguientes potencias: [pic], [pic], [pic], [pic],… donde lasoperaciones matriciales se definen de la siguiente forma:

a. Si se trata de hallar la trayectoria de valor mínimo:
El producto de las dos matrices dará origen a otra matriz C obtenida así:[pic]

Ósea que en la matriz C resultante cada uno de sus elementos es el mínimo de las parejas de sumas de los elementos de las filas de la primera matriz con los elementos de las columnas delas segunda matriz.

b. Si se trata de hallar la trayectoria de valor máximo:
Los elementos de la matriz producto son de la forma:

[pic]

Ósea que en la matriz C resultante cada uno desus elementos es el máximo de las parejas de sumas de los elementos de las filas de la primera matriz con los elementos de las columnas de las segunda matriz.

Ejemplo:
Determinar los valores delas trayectorias más cortas de todos los nodos del siguiente grafo.
[pic]

Paso 1: La matriz de valores asociados al grafo es:

A B C D E...
tracking img