1
UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
PROBLEMA DE LA RUTA MAS CORTA:
ALGORITMO DE DIJKSTRA
ALGORITMO DE FLOYD
Elaborado por: Angel Noel Illachura Sanchez
Revisado por: Dr. Manuel Alvarado Contreras
Tacna – Peru
Julio de 2018
2
INDICE
I. INTRODUCCION…………………………………………………..…………..….….4
1.1 OBJETIVOS……………………………………………………….………….5
II. MARCO TEÓRICO
2.1 CONOCIMIENTOS PREVIOS………………………………………….…6
2.1.1 TEORIA DE GRAFOS………..…………...................6
2.2 ANTECEDENTES………………………………………………….……….13
2.3 PROBLEMA DE LA RUTA MAS CORTA………………………….........19
2.3.1DEFINICIÓN…………………………...…………………...….....19
2.3.2FINALIDAD………………………………………………...……..20
2.4 ALGORITMO DE DIJKSTRA………………………………...………….…21
2.4.1 DESCRIPCION…………………………….… …...….21
2.4.2 COMPLEJIDAD……………………………………….21
2.4.3APLICACIONES……………….…………………...….21
2.4.4ALGORITMO…………….…………………………….22
2.4.5 EJEMPLO CON WINQSB……….………………...…22
2.5 ALGORITMO DE FLOYD……………………………….…………...……23
2.5.1 DESCRIPCION………………………………………………27
2.5.2 COMPLEJIDAD…………………………….………….…….27
2.5.3APLICACIONES………………………………….…….…….27
2.5.4ALGORITMO…………………………………………………28
2.5.5EJEMPLO CON WINQSB ……………………..……………29
III. CONCLUCIONES…………………………………………………………...............…33
IV. REFERENCIAS…………………………………………..............…………………….33
3
RESUMEN
El problema del camino más corto es un caso aplicativo muy importante de
la teoría de grafos, el problema consiste en encontrar un camino de tal manera que
las sumas de sus pesos sean mínimas, para ello se puede usar definiciones de teoría
de grafos para hallar el camino optimo, pero se nos hace más cómodo y factible
trabajar con dos algoritmos, el algoritmo de dijkstra y el algoritmo de Floyd, los
cuales nos permiten hallar el camino más corto y con el costo mínimo en el caso
de dijkstra.
ABSTRACT
The problem of the shortest path is a very important application case of the
graph theory, the problem is to find a way in such a way that the sums of their
weights are minimal, for this you can use definitions of graph theory to find the
optimal path , but it makes us more comfortable and feasible to work with two
algorithms, the algorithm of Dijkstra and the algorithm of Floyd, which allow us
to find the shortest way and with the minimum cost in the case of Dijkstra.
4
I. INTRODUCCION
Un fenómeno surgió con el avance de los tiempos, el fenómeno de
las comunicaciones, y con ello la necesidad de acelerar los procesos de
comunicaciones, por ejemplo. Encontrar direcciones de forma automática
entre lugares físicos, como las rutas de conducción en sitios de mapas
web como google maps. Para estas aplicaciones están disponibles
algoritmos especializados, como en los que vamos a estudiar en esta
monografia.
El algoritmo de dijkstra fue descubiertopor Edsger dijkstra en
1956, su desarrollo fue mediante el lenguaje de programación ALGOL,
a demás del algoritmo que conocemos desarrollo otros algoritmos como
por ejemplo el algoritmo de shunting yard. El algoritmo de Floyd fue
descubierto por .
Primero repasaremos un poco lo que es pieza importante para
entender con claridad el tema nos referimos a la teoría de grafos. Luego
estudiaremos el problema del camino más corto dando su definición e
importancia, siguiendo con el esquema estudiaremos los algoritmos
mencionados dando su descripción, su importancia, sus aplicaciones,
sus seudocódigos, proseguiremos dando un ejemplo en ambos casos, y
5
nos ayudaremos del software WINQSB para evitar el tedioso proceso
de las iteraciones.
Recomendamos revisar el libro Análisis Cuantitativo con Winqsb
para poder entender mejor el procedimiento de los ejemplos.
1.1 OBJETIVOS
Determinar el costo del menor camino desde una fuente hasta un origen
Hacer entender al lector sobre las diferentes tipos de algoritmos
expuestos.
Adaptar el tema a los problemas y necesidades de la sociedad
6
II. MARCO TEORICO
2.1CONOCIMIENTOS PREVIOS
2.1.1 TEORIA DE GRAFOS1
Un grafo es un par G=(V,A), donde V es un conjunto finito no vacío
(a cuyos elementos llamaremos vértices) y A es una familia finita de pares no
ordenados de vértices de V (a cuyos elementos llamaremos aristas o arcos).
Un grafo simple es un par G=(V,A) donde V es un conjunto finito no vacío y
A es un conjunto finito de pares no ordenados de vértices distintos de V.
Si a={u,v} es una arista de G escribiremos sólo a=uv, y diremos
que a une los vértices u y v o que u y v son extremos de a. Una arista a=uu se
llama bucle. Una arista que aparece repetida en A se llama arista múltiple.
(En otros textos llaman grafo al que aquí se denomina grafo simple,
permitiendo la presencia de aristas múltiples en los multigrafos y de bucles en
los seudografos).
Dos vértice son adyacentes si son extremos de una misma arista. Dos
aristas son adyacentes si tienen un extremo común. Un vértice y una arista
son incidentes si el vértice es extremo de la arista. Un vértice es aislado si no
tiene otros vértices adyacentes.
1
[Link] Carrasco, “Grafos”, [Link].
7
Un grafo completo es un grafo simple en el que todo par de vértices
está unido por una arista. (Se representa con Kn al grafo completo de n
vértices).
Un grafo G=(V,A) se llama bipartito (o bipartido)si existe una
partición de V, V=XÈY, tal que cada arista de G une un vértice de X con otro
de Y. (Se designa por Kr,s al grafo bipartito completo en que ½X½= r
e ½Y½= s, y hay una arista que conecta cada vértice de X con cada vértice de
Y)
El nº de vértices de un grafo G es su orden y el nº de aristas su tamaño.
Designaremos el orden con n y el tamaño con q y utilizaremos la notación de
grafo (n,q).
Dos grafos G=(V,A) y G’=(V’,A’) son isomorfos si existe una
biyección f:V®V’ que conserva la adyacencia. (Es decir, " u,vÎV, u y v son
adyacentes en G Û f(u) y f(v) son adyacentes en G’.
Un subgrafo de G=(V,A) es otro grafo H=(V’,A’) tal que V’ÍV y
A’ÍA. Si V’=V se dice que H es un subgrafo generador.
Se llama grado de un vértice v al número de aristas que lo tienen como
extremo, (cada bucle se cuenta, por tanto, dos veces). Se designa por d(v)
Un grafo regular es un grafo simple cuyos vértices tienen todos el
mismo grado.
8
A la sucesión de los grados de los vértices de G se le
denomina sucesión de grados del grafo G. Una sucesión de enteros no
negativos se dice sucesión gráfica si es la sucesión de grados de un grafo
simple.
El menor término de la sucesión de grados es el grado mínimo de G y
se designa por d(G). El mayor es el grado máximo y se designa por D(G)
Propiedades:
1) La relación entre los grados y el número de aristas en G
es:
2) Hay grafos no isomorfos con la misma sucesión de grados
3) La sucesión (d1,d2,...,dn) es la sucesión de grados de un
grafo Û Sdk es par.
4) Para grafos simples se tiene que:
la sucesión no creciente (s,t1,...,ts,d1,...dr ) es gráfica Û lo es la
sucesión (t1 -1,...,ts -1,d1,...dr )
Matrices:
La matriz de adyacencia de un grafo G con n vértices {v1,...,vn} es la
matriz nxn , M(G)=(aij), donde aij es el nº de aristas que unen vi con vj.
9
La matriz de incidencia de un grafo simple G con n vértices {v1,...,vn} y k
aristas {e1,...,ek} es la matriz nxk, I(G)=(bij), donde bij=1 si vi es incidente con
ej y bij=0 en caso contrario.
Caminos y conexión:
Un recorrido en un grafo es una sucesión de vértices y aristas de la
forma v0 a1 v1 a2...vk-1 ak vk donde la arista ai une los vértices vi-1 y vi. Éste es un
recorrido de v0 a vk, de longitud k, siendo v1,...,vk-1 los vértices interiores del
camino. Si v0=vkdecimos que el recorrido es cerrado (en ocasiones se le llama
circuito). Un camino en un grafo es un recorrido en el que no se repiten
vértices ni aristas. Un ciclo es un camino cerrado.
Propiedades:
1) El nº de recorridos de longitud k de vi a vj es el elemento ij de la
matriz M(G)k.
2) Un grafo G es bipartito Û G no tiene ciclos de longitud impar.
3) Si G tiene sólo dos vértices impares existe un camino entre ellos.
Un grafo es conexo si para cada par de vértices u y v existe un camino
de u a v. Si G es un grafo no conexo (o disconexo), cada uno de sus subgrafos
conexos maximales se llama componente conexa de G.
Designaremos por k(G) al nº de componentes conexas del grafo G
10
Un vértice v se llama vértice-corte (o punto de articulación) de G si el
grafo G-{v} tiene más componentes conexas que G.
Una arista a de un grafo G se llama puente si G-{a} tiene más
componentes conexas que G.
Los bloques de un grafo G son los subgrafos de G sin vértices-corte y
maximales con respecto a esta propiedad.
Propiedades:
1) Una arista e de un grafo conexo es un puente de G Û la arista e no
pertenece a ningún ciclo de G.
2) Si dos bloques comparten un vértice, éste debe ser un vértice-corte
Digrafos
Un digrafo o grafo dirigido es un par D=(V,A) donde V es un
conjunto no vacío (a cuyos elementos llamaremos vértices) y A es una familia
finita de pares ordenados de vértices de V (a cuyos elementos
llamaremos aristas o arcos).
11
Un digrafo simple es un par D=(V,A) donde V es un conjunto no vacío
y A es un conjunto finito de pares ordenados de vértices distintos de V.
Si a=(u,v) es un arco escribiremos a=uv, y diremos que u es extremo
inicial de a y que v es extremo final de a.
Se llama grado de entrada de un vértice v al número de arcos que lo
tienen como extremo final y se llama grado de salida de v al número de arcos
que lo tienen como extremo inicial.
La matriz de adyacencia de un digrafo D con n vértices {v1,...,vn} es
una matriz nxn, M(D)=(aij) donde es el número de arcos que tienen a vi como
extremo inicial y a vj como extremo final.
Un camino dirigido en un digrafo es una sucesión de vértices y arcos
de la forma v0e1v1e2...vn-1 envn , donde el arco ei tiene como extremos inicial y
final vi-1 y vi , respectivamente. Dicho camino se llama camino de v0 a vn y
su longitud es n.
Conexión. Grafos orientables.
Un digrafo D=(V,A) es fuertemente conexo si para todo par de
vértices u y v existe un camino dirigido que va de u a v.
12
Dado un digrafo D, podemos considerar el grafo G no dirigido que se
obtiene al sustituir cada arco (u,v) por la arista (u,v). Si este grafo es conexo,
diremos que el digrafo D es débilmente conexo.
Si en un grafo G, no dirigido, (por ejemplo, las calles de una ciudad),
se asigna un sentido a cada arista se obtiene una orientación de G.
Necesitamos, naturalmente, que se pueda ir desde cualquier punto de la ciudad
a cualquier otro, es decir, que el digrafo obtenido sea fuertemente conexo.
Cuando ésto se puede conseguir decimos que G es un grafo orientable.
Caracterización:
G es orientable Û G es conexo y sin puentes.
13
2.2 ANTECEDENTES
(Mendez Martinez, Rodriguez, & Medina Ramirez, 2013) (UAM)
“TOMA DE DECISIONES BASADAS EN EL ALGORITMO DE
DIJKSTRA
Una Solución para Radios Cognitivos”
Una de las funciones que realiza un ‘Radio Cognitivo’ es la toma de
decisiones sobre el espectro radioeléctrico, esto a partir del análisis que realiza de
su entorno. En este trabajo de investigación, se propone un método para la toma
de decisiones para la selección de una banda en el espectro radioeléctrico que
cumpla con ciertos criterios requeridos para una aplicación. Esta toma de
decisiones se basa en un algoritmo de búsqueda del camino más corto similar al
Algoritmo de Dijkstra. Para encontrar el camino más corto, el cual representa a la
banda de frecuencia requerida, se especifican los atributos o parámetros a
considerar para cada una de las bandas de acuerdo a una aplicación en particular
o servicio requerido. A estos atributos o parámetros se les asignan valores es decir,
pesos que determinan la prioridad e importancia para cada servicio. El algoritmo
propuesto basado en Dijkstra, evalúa los parámetros del conjunto de bandas
disponibles considerando el peso asignado, e indica la banda a seleccionar y que
cubre con los criterios de la toma de decisiones. Se realizaron simulaciones por
computadora para caracterizar los servicios identificados como mejor esfuerzo
‘Best Effort’ y tiempo real ‘Real Time’, obteniendo como resultado una latencia
reducida que representa un tiempo práctico para ser implementado en un Radio
Cognitivo en su toma de decisiones. Se observó también que los tiempos
14
mostraron una mejora al ser comparados con los resultados obtenidos al
implementar el Algoritmo de AHP.
Los resultados obtenidos con la propuesta del Algoritmo de Toma de
Decisiones con Dijkstra Modificado (ATDDiM) muestran una reducción en los
tiempos de ejecución con respecto a los algoritmos AHP1 y Dijkstra. Durante la
simulación se consideraron cuatro atributos para evaluar los servicios Best Effort y
Real Time, para determinar la banda que se adapta mejor a los requerimientos
solicitados para cada caso. Además, el modelo propuesto puede adaptarse a
diferentes atributos, así como ajustarse a un número mayor de atributos, teniendo en
cuenta que se deberán ajustar la asignación de pesos o prioridades de acuerdo al
servicio solicitado o disponible.
Nuestra simulación muestra que el algoritmo propuesto puede utilizarse en
la Toma de Decisiones en un Radio Cognitivo ya que presenta tiempos de latencia
que se pueden llevar a la práctica. Además, no presenta un incremento significativo
en el tiempo de selección cuando se incrementa el número de bandas evaluadas, esto
comparado con los algoritmos de AHP1 y Dijkstra.
Como trabajo futuro se planea implementar la propuesta con valores
experimentales de la detección de energía y llevarlo a una aplicación utilizando
radios programables (GNU-Radios).
(HERNAN & SANCHEZ, 2004) UNIVERSIDAD TECNOLOGICA DE
PEREIRA
15
“APLICACIÓN DE LA TEORIA DE GRAFOS Y EL ALGORITMO
DE DIJKSTRA PARA DETERMINAR LAS DISTANCIAS Y LAS RUTAS
MAS CORTAS EN UNA CIUDAD”
El objetivo de este trabajo es representar la malla vial de la ciudad de santa
rosa de Cabal por medio de una matriz de incidencia y se determina las distancias y
rutas mas cortas entre una intersección de vías y otra cualquiera, utilizando el
algoritmo de dijkstra.
Concluimos que un aspecto importante, fue la construcción de la matriz de
distancias minimas entre todos los nodos que representan la ciudad. Los resultados
encontrados con este proyecto son de gran valor, pues son la fuente de datos para
resolver problemas que requieran conocer las distancias minimas entre diferentes
lugares como: La entrega del periódico, la entrega de encomiendas, la ruta mas corta
que debe seguir el vehiculo del cuerpo de bomberos para atender una emergencia y
el conflicto que enfrentan las empresas que suministran productos tiendad a tienda
entre otros.
16
(PEÑARANDA ORTEGA , QUIÑONES VIDAL,
& LOPEZ GARCIA, 2006)
“Los «Small Worlds» y el algoritmo de
Floyd: una manera de estudiar la
colaboración científica”
Desde el análisis de las redes sociales aplicadas al estudio de
la colaboración científica se han realizado numerosas
propuestas en los últimos años. La teoría Small Worlds parece
ser la que obtiene un perfil más eficaz para estudiar las
características propias de la comunidad científica. Lo que
todos estos estudios han demostrado es que las comunidades
pequeñas se basan en unos cuantos individuos clave que
vinculan a unos grupos que, de lo contrario, estarían
desconectados. Uno de los inconvenientes desde la
perspectiva del análisis de redes es la falta de estudios sobre
los nodos particulares. Con la implementación de un
pseudocódigo algoritmo de Floyd tratamos de salvar esta
carencia. También, y como estudio de un caso, observamos el
colegio invisible que se conformaría al unir los 15 autores más
productivos del Journal of Personality and Social Psychology,
explicando de esta manera cómo se configura una comunidad
pequeña.
Numerosos autores han enfatizado la eficacia del análisis de redes sociales
para el estudio de la colaboración científica, especialmente desde la teoría Small
17
Worlds (Barabási et al, 2002; Newman, Barabási y Watts, 2003; Watts, 1999). De esta
forma, se comprueba que la Ciencia no es más que la mera unión de ramas científicas
más alejadas o separadas entre sí, pero englobadas al fin y al cabo en el mismo plano
(Tvire y Erno, 2001). Desde este punto de vista, los autores investigan y firman los
trabajos conjuntamente, estableciendo una estrecha relación entre sí, y quedando
vinculados con otros autores que, no habiendo publicado directamente con ellos, sí lo
han hecho con sus colaboradores más directos. Esta red de relaciones sociales
establece grupos coherentes y permanentes de trabajo, con intereses y finalidades bien
definidas, tanto teórica como metodológicamente (Carpintero y Peiró, 1981).
Se ha comprobado que la implementación de un algoritmo en el estudio de la
colaboración científica simplifica enormemente el cálculo de longitud entre rutas de
nodos, lo cual es muy beneficioso en el análisis de la colaboración científica y la
visibilidad de sus autores. Este tipo de procesos se ha mostrado muy revelador en otros
tipos de exploraciones con gran cantidad de datos (Pitarque et al, 1997).
El algoritmo de Floyd es una herramienta precisa en el cálculo de los caminos
más cortos a trazar para el análisis de las publicaciones entre diferentes autores, incluso
desde diferentes materias o áreas de conocimiento, ya que, como se ha mostrado,
permite analizar una enorme red de nodos. La entrada en un mundo «Small Worlds» de
coautoría científica vendría a ser relativamente fácil si se cumplen ciertos criterios de
publicación y firmas conjuntas con otros autores, aunque la cadena sería relativamente
extensa si analizásemos autores que han publicado en reducidas ocasiones.
Por contra, cuando se detecta una colaboración, permanece a lo largo del
tiempo, tanto si esa relación científica tuvo su fin o continúa, ya que el algoritmo de
Floyd mantiene esa información, por lo que para el tipo de crecimiento que tuvo esa
18
comunidad se debería de parcelar la observación del Small World tomando los datos
en cortes temporales, dotándolo así de cierta dinamicidad.
Una carencia que hemos encontrado desde este tipo de estudio es que, para
análisis cualitativos de intensidad en la productividad, como conocer el tipo de unión
que afecta a los nodos y la potencia que tendría a nivel productivo, el algoritmo de
Floyd no puede discriminar las posibles diferencias entre autores con mayor o menor
relevancia productiva entre ellos, por lo que, en un nivel superior de análisis, y
referido al análisis de científicos que publican sus obras y no a números de nodos
que estima un computador, quedaría patente esta limitación cualitativa de la red
(Adamic y Adar, 2003). Si se introdujera un cambio en el cual se especificara el tipo
de enlace que une cada nodo respecto del resto conforme su tamaño en
productividad, esta circunstancia seria obviada
19
2.3PROBLEMA DE LA RUTA MAS CORTA
2.3.1. DEFINICION
El problema del camino más corto puede ser definido para grafos no
dirigidos, dirigidos o mixtos. La siguiente es una definición para grafos no
dirigidos, en el caso de grafos dirigidos la definición de camino requiere que
los vértices adyacentes estén conectados por una apropiada arista dirigida.
Dos vértices son adyacentes cuando poseen una arista común.
Un camino en un grafo no dirigido es una secuencia de
vértices tal que todo vértice
es adyacente con el vértice 𝑣𝑖+1 . Un camino se dice que es
de longitud n si va desde 𝑣1 hasta 𝑣𝑛 .
Sea 𝑒𝑖𝑗 la arista incidente con los vértices 𝑣𝑖 y 𝑣𝑗 . Dada una función
de variable real ponderada 𝑓: 𝐸−→ 𝑅 y un grafo no dirigido V, el camino
más corto desde v hasta v’ es el camino 𝑝 = (𝑣1 , 𝑣2 , … , 𝑣𝑛 ) (donde 𝑣1 =
𝑣 y 𝑣𝑛 = 𝑣′ ) sobre todos los posibles n que minimiza la
suma ∑𝑛−1
𝑖=1 𝑓(𝑒𝑖 , 𝑖 + 1). Cuando cada arista en el grafo tiene un peso unitario
o 𝑓: 𝐸−→ {1} , hallar el camino más corto es equivalente a encontrar el
camino con menor número de aristas.( [Link] Carrasco, “Grafos”,1996)
20
2.3.2 FINALIDAD
El problema es también conocido como el problema de los caminos más
cortos entre dos nodos, para diferenciarlo de las siguientes
generalizaciones:
El problema de los caminos más cortos desde un origen, en el cual
tenemos que encontrar los caminos más cortos de un vértice
origen v a todos los demás vértices del grafo.
El problema de los caminos más cortos con un destino, en el cual
tenemos que encontrar los caminos más cortos desde todos los
vértices del grafo a un único vértice destino, esto puede ser reducido
al problema anterior invirtiendo el orden.
El problema de los caminos más cortos entre todos los pares de
vértices, el cual tenemos que encontrar los caminos más cortos entre
cada par de vértices (v, v') en el grafo.
21
2.4 ALGORITMO DE DIJKSTRA
2.4. 1 DESCRIPCION
El algoritmo Dijkstra o también llamado algoritmo de caminos
mínimos, es un algoritmo eficiente para la determinación del camino más
corto dado un vértice origen al resto de vértices en un grafo con pesos en
cada arista. Éste se encarga de formar un camino a partir de otro ya
existente.
El algoritmo Dijkstra trabaja por etapas bajo el principio de la
optimalidad, tomando en cada etapa la mejor solución sin considerar
consecuencias futuras; donde el óptimo encontrado puede modificarse
posteriormente si surge una solución mejor. El algoritmo devuelve en
realidad el peso mínimo, no el camino mínimo propiamente dicho.
Prawda,( 1976) Metodos y Modelos de Investigacion de
Operaciones
2.4.2 COMPLEJIDAD
El algoritmo es de orden O(n^2). Si se usa una matriz de distancia
para representarla, cada ciclo toma tiempo O(n) y son ejecutados n-1 veces.
Si se emplea lista de adyacencia para representar la diagrafica el tiempo de
recorrido será del orden de O(Log n ) y el tiempo de los ciclos será del orden
de O ( A log n)
22
2.4.3 APLICACIONES
Seleccionar la ruta mas corta entre dos ciudades: cada ciudad se
representa con los vértices y las aristas representan la duración de los
vuelos.
Utilizado en redes en protocolos de enrutamiento dinamico como OSPF
y IS –IS
2.4.4 PSEUDOCODIGO
Paso 1. Sea 𝑁𝑠 el nodo fuente. Entonces 𝐿′𝑠𝑘 = 𝐶𝑠𝑘 para todo 𝐴𝑠𝑘 que
este definido en la red. El nodo 𝑁𝑠 pasa a ser un elemento del árbol. Se
define 𝐿𝑠𝑠 ≡ 0.
Paso 2. Sea
𝑀𝑖𝑛{𝐿′ 𝑠𝑘 } 𝑀𝑖𝑛[𝐿𝑠𝑗 + 𝐶𝑗𝑘 ]
𝐿𝑠𝑟 = =
𝑘 𝑘
Donde 𝑁𝑘 son todos los nodos vecinos a los nodos del
árbol en cuestión.
Paso 3. El arco 𝐴𝑗𝑟 pasa a ser un elemento del árbol. Se etiqueta al nodo 𝑁𝑟 con
(𝐿𝑠𝑟 , 𝑁𝑖 ).
Paso 4. Si el árbol tiene n-1 arcos, pare, la solución optima ha sido
encontrada. En caso contrario continue con el paso 5.
23
Paso 5. Sea
𝑀𝑖𝑛{𝐿′ 𝑠𝑘 , 𝐿𝑠𝑟 + 𝐶𝑟𝑘 }
𝐿′𝑠𝑘 =
𝑘
Para todos los nodos 𝑁𝑘 vecinos a los nodos del árbol .
Regrese al paso 2.
Prawda,( 1976) Metodos y Modelos de Investigacion de
Operaciones,1,347-351.
2.4.5 EJEMPLO con WINQSB
Alejandro desea ir a un centro comercial al otro lado de la ciudad para
poder acudir a una reunión de trabajo. Para conocer la ruta que podría tomar
ingresa en una aplicación móvil donde localiza su ubicación y la del centro
comercial; en ella se percata que existen 5 calles que puede tomar. En la
aplicación se muestra los km de cada calle que es una conexión directa entre
dos calles. Estas distancias se encuentran resumidas en la tabla n°1, donde los
guiones señalan la inexistencia de conexión directa entre las calles.
SOLUCION:
24
Tabla N°1
Fuente : Propia
Ingresamos los datos de la tabla n°1 al programa
Finalmente, el software arroja la ruta más corta, a través de una tabla
(tabla n°2) como esta:
Tabla N°2
Fuente : winqsb
25
Con el programa también podemos conocer el camino optimo (cuadro N°1).
Cuadro N°1
Fuente: winqsb
26
Interpretación de la salida obtenida del software WinQSB:
De la tabla N°2 y el cuadro N°1 que arroja WinQSB se puede mencionar que
para que Alejandro llegue a tiempo a la reunión que se realizará en el centro
comercial, la ruta más corta es salir de su casa tomar la calle a, luego la calle
b, la calle d y por último llegar al centro comercial, quedando así la distancia
entre la casa de Alejandro y el centro comercial 165 km.
27
2.5 ALGORITMO DE FLOYD
2.5.1 DESCRIPCION
A veces no es suficiente calcular las distancias con respecto a un
vértice s, si no que necesitamos conocer la distancia entre cada par de
vértices. Para ello se puede aplicar reiteradamente alguno de los algoritmos
anteriores, variando el vértice s de partida. Así tendríamos algoritmos de
complejidad O(n3) (si usamos el algoritmo de Dijkstra) u O(n2q) (si usamos
el algoritmo de Ford). A continuación se describe un algoritmo, debido a
Floyd y Warshall, con una estructura sencilla, que permite la presencia de
arcos de peso negativo y que resuelve el mismo problema. (Naturalmente
los ciclos de peso negativo siguen estando prohibidos).
[Link],( 2004) Investigacion de Operaciones
2.5.2 COMPLEJIDAD
Se deben construir n matrices de tamaño nxn y cada elemento se
halla en tiempo constante. Por tanto, la complejidad del algoritmo es O(n3)
2.5.3 APLICACIONES
Seleccionar la ruta mas corta entre dos ciudades: cada ciudad se
representa con los vértices y las aristas representan la duración de los
vuelos.
28
Utilizado en redes en protocolos de enrutamiento dinamico como OSPF
y IS -IS
2.5.4 PSEUDOCODIGO
El algoritmo de Floyd es más general que el de Dijkstra, ya que
determina la ruta más corta entre dos nodos cualquiera de la red.
El algoritmo representa una red de n nodos como una matriz cuadrada de
orden n, la llamaremos matriz C. De esta forma, el valor Cij representa el
coste de ir desde el nodo i al nodo j, inicialmente en caso de no existir un
arco entre ambos, el valor Cij será infinito.
Definiremos otra matriz D, también cuadrada de orden n, cuyos elementos
van a ser los nodos predecesores en el camino hacia el nodo origen, es
decir, el valor Dijrepresentará el nodo predecesor a j en el camino mínimo
desde i hasta j. Inicialmente se comienza con caminos de longitud 1, por
lo que Dij = i.
Las diagonales de ambas matrices representan el coste y el nodo
predecesor para ir de un nodo a si mismo, por lo que no sirven para nada,
estarán bloqueadas.
Los pasos a dar en la aplicación del algoritmo de Floyd son los
siguientes:
Paso 1. Formar las matrices iniciales C y D.
Paso 2. Se toma k=1.
29
Paso 3. Se selecciona la fila y la columna k de la matriz C y entonces,
para i y j, con i≠k, j≠k e i≠j, hacemos:
Si (Cik + Ckj) < Cij → Dij = Dkj y Cij = Cik + Ckj
En caso contrario, dejamos las matrices como están.
Paso 4. Si k ≤ n, aumentamos k en una unidad y repetimos el paso anterior,
en caso contrario paramos las iteraciones.
La matriz final C contiene los costes óptimos para ir de un vértice
a otro, mientras que la matriz D contiene los penúltimos vértices de
los caminos óptimos que unen dos vértices, lo cual permite
reconstruir cualquier camino óptimo para ir de un vértice a otro.
([Link],[Link],( 2004) Investigacion de Operaciones)
2.5.5EJEMPLO CON WINQSB
Aplicar el algoritmo de Floyd sobre el siguiente grafo para obtener las
rutas más cortas entre cada dos nodos. El arco (3, 5) es direccional, de manera que no está
permitido ningún tráfico del nodo 5 al nodo 3 . Todos los demás arcos permiten el tráfico en ambas
direcciones.
30
Solución:
Las conexiones se mostraran en la siguiente tabla (tabla n°3)
Tabla N°3
1 2 3 4 5
1 - 3 10 8 8
2 3 - 8 5 8
3 10 8 - 6 15
4 8 5 6 - 4
5 8 8 8 4 -
Fuente : Propia
Ingresamos los datos de la tabla N°1 al software
31
Finalmente, el software arroja la ruta más corta, a través de una tabla
(tabla n°4) como esta:
Tabla N°4
Fuente : winqsb
Con el programa también podemos conocer el camino optimo (cuadro N°2).
Cuadro N°2
32
Fuente: winqsb
Interpretación de la salida obtenida del software WinQSB:
De la tabla N°4 y el cuadro N°2 que arroja WinQSB se puede mencionar que
cualquier camino que tomen los nodos para llegar a uno de ellos será el
optimo.
33
III. CONCLUSIONES
No podemos utilizar el mismo algoritmo en todos los problemas, para ellos
debemos utilizar el algoritmo adecuado para encontrar la ruta mas corta a través de
la red, que se presentan con distancia reales. Por ejemplo, si tenemos pesos negativos
es decir ingresos, no podríamos utilizar el algoritmo de dijkstra.
En el estudio de los algoritmos nos dimos cuenta que estos pueden ser
formulados como modelos de programación lineal, luego resuelto con el método
simplex, pero no es conveniente su utilización. Por otro lado, solucionar el problema
utilizando redes mejora la eficiencia de los cálculos.
IV. REFERENCIAS
[Link] A. Taha (2004). Investigación de Operaciones, 7ª edición.
México: Pearson Educación.
Manuel Alvarado, Ramón Vera. Investigación de Operaciones. Perú:
Editorial S.A
Juan Prawda (1976). Métodos y Modelos de Investigación de Operaciones
vol1. Modelos determinísticos. México: Editorial Limusa
Manuel de los Reyes, Jose Romero (1992). Investigación de Operaciones I,
1ra edición. México: Azcapotzalco biblioteca
Roberto Carro (2009). Investigación de operaciones en administración
edición 2009. Argentina: Editorial Pincu
