Embedded Files
Qué es un grafo y para que sirve
Qué es un grafo y para que sirve
Sabiendo que un grafo es la representación simbólica de los elementos constituidos de un sistema o conjunto mediante esquemas gráficos y lo que es la teoría de grafos podemos ver que sirve para resolver diversos problemas:
Síntesis de circuitos secuenciales: los circuitos secuenciales pueden entenderse simplemente como un circuito combinacional en el cual las salidas dependen tanto de las entradas como de las salidas en instantes anteriores, lo que implica una retroalimentación de las salidas.
Dibujo computacional: técnica usada para la ejecución de sistemas de proceso computacional. Mediante hardware y software se lleva a cabo la transcripción para convertir los movimientos en una señal de entrada continua (analógica), a valores numéricos (digital). Se usa en áreas como la ingeniería, arquitectura, construcción...
Modelaje de trayectos: como el de una línea de autobús recorriendo las calles de una ciudad, se pueden obtener caminos óptimos para el trayecto aplicando diversos algoritmos como el algoritmo de Floyd.
Algoritmo de Floyd
Algoritmo de Floyd
Robert W. Floyd nació en 1936 en Nueva York y fue un importante científico estadounidense en informática, se graduó en la Universidad de Chicago a los17 años y como físico en 1958.
En 1978 fue otorgado el prestigioso Premio Turing que concede la ACM para reconocer las contribuciones de naturaleza técnica realizadas a la comunidad informática.
El algoritmo de Floyd Warshall
El algoritmo de Floyd Warshall
El problema que quiere resolver este algoritmo es el de encontrar el camino más corto entre dos pares de vértices o nodos de un grafo. Esto se asemeja a construir un mapa con distancias mínimas entre pares de ciudades, indicando la ruta a seguir para ir de la primera a la segunda ciudad. Este es uno de los problemas que se pueden resolver con la teoría de grafos.
Existen varias soluciones para este problema y los algoritmos a utilizar varían segun la existencia de arcos con pesos o costes negativos en el grafo. En el caso de no exisitr pesos negativos sería posible ejecutar el algoritmo de Dijkstra para obtener el cálculo del camino mínimo.
El algoritmo de Floyd Warshall ideado por Floyd en 1962, usa la metodología de Programación Dinámica para resolver el problema. Este puede resolver el problema con pesos negativos y tiempos de ejecución específicos, sin embargo el algoritmo tiene problemas con los ciclos de peso negativo.
Este algoritmo se puede utilizar para resolver multitud de problemas, incluyendo el diseño de circuitos, el diseño de rutas de transporte o como base de otros algoritmos más complejos.
Camino más corto entre nodos
Camino más corto entre nodos
Ahora veremos cómo hallar el camino más corto entre dos nodos en un grafo ponderado. Para resolver este problema utilizaremos distintos algoritmos dependiendo de cuál sea nuestro objetivo y el tipo de grafo con el que estemos trabajando.
Dijkstra
Dijkstra
La manera más común para hallar el camino mas cortos entre dos pares de nodos de un grafo con pesos no negativos es usando el algoritmo de Dijkstra. La idea principal es ir construyendo un grafo F, inicialmente formado solo por el nodo origen. En cada paso miraremos todos los nodos a los que se puede llegar directamente desde F, es decir, aquellos que comparten arista con un nodo de F, y añadiremos el nodo cuya distancia de origen sea mínima. Finalizaremos el algoritmo en el momento en el que el vértice a incluir a F sea el nodo destino.
Ejemplo:
Ejemplo:
Teniendo en cuenta el grafo a la derecha usaremos el algoritmo para hayar el camino más corto entre los nodos 1 y 6.
Podemos observar que la distancia mínima entre 1 y 6 es 7. Teniendo en cuenta que a cada paso añadimos los nuevos arcos viendo la distancia al nodo origen.
Observaciones:
En este caso el algoritmo ha dado lugar a un camino pero en principio puede dar lugar a cualquier tipo de árbol.
El algoritmo funciona siempre que no haya pesos negativos, si los hubiera habría que resolverlo con un algoritmo diferente.
En este caso el grafo no era dirigido pero si lo fuera también se podría resolver con este algoritmo.
Al usar el algoritmo de Dijkstra estamos calculando la distancia mínima entre u y cualquier nodo que se encuentre más cerca que v. Es decir, con la misma dificultad podemos encontrar la distancia de un nodo a todos los demás.
Floyd Warshall
Floyd Warshall
Ahora vamos a suponer que tenemos que calcular la distancia mínima entre todos los pares de vértices de un grafo ponderado. Se podría calcular con el algoritmo de Dijkstra pero si los pesos son negativos este algoritmo no se podría utilizar tendríamos que utilizar el algoritmo de Bellman-Ford, pero se puede calcular más rápido utilizando el algoritmo de Floyd Warshall, el cual admite pesos negativos siempre y cuando no haya ciclos negativos.
La idea de este algoritmo es parecida a la de Bellman-Ford. Se van a realizar n interacciones, en cada interacción se considerarán los caminos óptimos que tienen como nodos intermedios aquellos con índice menor a i (si los vértices están numerados de o a n-1; si estuviesen numerados de 1 a n entonces menor o igual a i). Entonces tras n interacciones habremos considerado los caminos óptimos que incluyen cualquier nodo, es decir, los caminos óptimos en general.
En este caso el grafo dado como matriz de adyacencia. Tendremos otra matriz (dist) de n filas y n columnas de modo que en la casilla dist guardaremos la mínima distancia del nodo i al j. Al igual que en el algoritmo de Bellman-Ford inicialmente el valor de todas las distancias es infinito, a excepción de aquellas en que exista un arco directo de i a j, en cuyo caso el peso de dist será el valor del arco. Realizaremos n interacciones, en cada una se consideran todas las parejas de nodos. Al haber considerado como "nodo intermedio" todos los n nodos del grafo habremos terminado.
Ejemplo
Ejemplo
Queremos hallar la mínima distancia entre cada par de nodos.
Interacción 0: inicialización de las distancias
Interacción 1: consideramos caminos que tienen 1 como nodo intermedio
Continuaremos haciendo este proceso hasta obtener todas las interacciones posibles.
Al final podremos observar la mínima distancia entre cada par de nodos.
Page updated
Report abuse