Analisis De Grafos

Estrategia Greedy El método codicioso consiste en tomar sucesivamente, las decisiones de modo que cada decisión individual sea la mejor de acuerdo con algún criterio limitado "a corto plazo" cuya evaluación no sea demasiado costosa. Una vez tomada una decisión, no se podrá revertir, ni siquiera si más adelante se hace obvio que no fue una buena decisión. Por esta razón, los métodos codiciosos no necesariamente hallan la solución óptima en muchos problemas. No obstante, en el caso de los problemas que se estudiaran en este capítulo, es posible demostrar que la estrategia codiciosa apropiada produce soluciones óptimas. En general la estrategia Greedy trabaja en fases. En cada fase, se realiza una decisión que aparentemente es la mejor, sin considerar o lamentar futuras consecuencias. Generalmente, esta idea es pensada como escoger algún óptimo local. Si se resume la estrategia como "toma lo que puedas obtener, ahora" podrá entender el porque del nombre de esta clase de algoritmos. Cuando el algoritmo termina tendremos la esperanza que el óptimo local es igual al óptimo global. Si este es el caso, entonces el algoritmo es correcto, de otra manera el algoritmo a generado una solución suboptimal. Si la "mejor" respuesta no es requerida entonces los algoritmos greedy son a menudo usados para generar respuestas aproximadas, en vez de usar algoritmos más complicados que requieren de otra estrategia para generar "la" respuesta correcta. En general la estrategia Greedy trabaja en etapas "Top-Down" realizando una elección greedy después de la otra. En resumen, la estrategia Greedy consiste de dos partes: 1. Subestructura Optimal 2. Partir con elección de óptimos locales y continuar haciendo elecciones localmente optimales, hasta que la solución es encontrada. Problemas Asociados a esta técnica : Arbol Expandido Minimal ( Minimum Spanning Trees) “Dado un grafo no-dirigido y conexo G = , donde cada arco tiene asociado una "longitud" o "peso", se desea un subconjunto T, de arcos E, tal que el grafo restante sea conexo si solamente los arcos en T son usados, y la suma de los pesos de los arcos es el más pequeño posible. Tal subconjunto debe formar un subgrafo que es un árbol, al cual se le llama Minimum Spanning Tree.” En el proceso de cambio de monedas, por ejemplo $15.530 puede expresarse en $15.530 = 1 * $10.000 + 1 * $ 5.000 + 1 * $ 500 + 3 * ($10). En total se requieren 5 elementos. Al hacer esto estamos seguro de que el número de billetes y monedas es el mínimo. (Problema de Planificación de Tareas) Dado los trabajos t 1, t 2, ... t n, con tiempos t’1, t‘2, ... t’n y un solo procesador. Cuál es la mejor forma de planificar esos trabajos a fin de minimizar el tiempo medio de terminación? (Código de Huffman) en la compresión de archivos. Un código de longitud fija de un alfabeto A= { a1 , a2 , ..., am } con m-letras es una expresión en donde cada letra ai = ci,1 ci,2 ...ci,n , en donde i= 1, ...m, y donde cada ci,j es un elemento de algún conjunto de símbolos. El conjunto C = { ci,1 ci,2 ...ci,n , tal que, i= 1, ...m, es llamado código de longitud fija de longitud n, y cada ci,1 ci,2 ...ci,,n es llamado código. Veamos con cierto detalle, como funciona esta estrategia en la resolución del problema de comprimir archivos.

Nociones basicas de los grafos

Los grafos pueden representarse estructuras de datos distintas. Los algoritmos que se aplican sobre ellos adoptan tiempos distintos dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso (cuando tiene muchas aristas) o disperso (muy pocas aristas). Sea G = (V, E) un grafo simple con n=|V|, m=|E|. Definiremos la densidad del grafo como:

Notar que 0 < d < 1, donde d=0 si todos los vértices son aislados y d=1 si el grafo es completo. Si d es cercano a cero se dice que el grafo es disperso y si d es cercano a 1 se dice que el grafo es denso. Las representaciones más utilizadas de representación de los grafos son: a. Representación por matriz de adyacencia b. Representación por listas de adyacencias La matriz de adyacencia es la forma más común de representación y la más directa. Consiste en una tabla de tamaño nxn, en que la que aij tendrá como valor 1 si existe una arista del vértice i al vértice j. En caso contrario, el valor será 0. Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 tanto la entrada aij como la entrada aji, puesto que se puede recorrer en ambos sentidos. Como se puede apreciar, la matriz de adyacencia siempre ocupa un espacio de n2, es decir, depende solamente del número de nodos y no del de aristas, por lo que será útil para representar grafos densos. Una lista de adyacencia consiste de una lista de los vértices del grafo y para cada vértice de una lista de sus vértices vecinos. Ejemplos:

Directed acyclic graph (DAG) Es un grafo dirigido con siglos no dirigidos, que es, para algún vértice v, no hay caminos dirigidos en que v sea el inicio y final. Orden topológico: ▪Orden topológico de un DAG G=(V,E) es un orden lineal de todos los vértices tal que si G contiene el arco (u,v), entonces u aparece antes que v en el orden. ▪Cuando se tienen muchas actividades que dependen parcialmente unas de otras, este orden permite definir un orden de ejecución sin conflictos. ▪Gráficamente se trata de poner todos los nodos en una línea de manera que sólo haya arcos hacia delante. Algoritmo: Topological_Orden(G) Llamar a DFS(G) para calcular el tiempo de término f[v] para cada vértice. Insertar cada nodo en una lista enlazada según su orden de término. Retornar la lista enlazada. Costo: O(V + E),

Búsqueda en profundidad Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado. Costo: O( | V | + | E | ) = O(bd) DFS(grafo G) PARA CADA vertice u ∈ V[G] HACER estado[u] ← NO_VISITADO padre[u] ← NULO tiempo ← 0 PARA CADA vertice u ∈ V[G] HACER SI estado[u] = NO_VISITADO ENTONCES DFS_Visitar(u) DFS-Visitar(nodo u) estado[u] ← VISITADO tiempo ← tiempo + 1 d[u] ← tiempo PARA CADA v ∈ Vecinos[u] HACER SI estado[v] = NO_VISITADO ENTONCES padre[v] ← u DFS_Visitar(v) estado[u] ← TERMINADO tiempo ← tiempo + 1 f[u] ← tiempo

Clasificación de las aristas o ejes y parentización

Otra propiedad interesante de depth-first search es que puede servir para clasificar las aristas del grafo G=(V,E). Esa clasificación de ejes puede ser usada para recoger importante información acerca del grafo. Por ejemplo, un grafo dirigido es acíclico si y solo si no tiene aristas de tipo “back”. Se pueden definir 4 tipos de aristas: •Tree edges: Son aristas del bosque generado por DFS. •Back edges: Son aquellas aristas que conectan un vértice u con un vértice v ancestro en el depth-first tree. •Forward edges: Son aquellas aristas que conectan un vértice u con un vértice v descendiente en el depth-first tree. •Cross edges: Son todos las demás aristas. Ellos pueden ir desde vértices en el mismo depthfirst tree, a lo largo de un vértice que no es ancestro de otro, o pueden ir de vértices de diferentes depth-first trees.

a) Resultado de DFS. b) Lema de parentización. c)Tipos de aristas en el DFS.

Búsqueda en anchura Es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol. Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución. El algoritmo no usa ninguna estrategia heurística. Costo: O( | V | + | E | ) = O(bd) Procedimiento: •Dado un vértice fuente s, Breadth-first search sistemáticamente explora los vértices de G para “descubrir” todos los vértices alcanzables desde s. •Calcula la distancia (menor número de vértices) desde s a todos los vértices alcanzables. •Después produce un árbol BF con raíz en s y que contiene a todos los vértices alcanzables. •El camino desde s a cada vértice en este recorrido contiene el mínimo número de vértices. Es el camino más corto medido en número de vértices. •Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a los nodos de distancia k, sólo tras haber llegado a todos los nodos a distancia k-1. Algoritmo: BFS(grafo G, nodo_fuente s) { // recorremos todos los vértices del grafo inicializándolos a NO_VISITADO, // distancia INFINITA y padre de cada nodo NULL for u ∈ V[G] do { estado[u] = NO_VISITADO; distancia[u] = INFINITO; /* distancia infinita si el nodo no es alcanzable */ padre[u] = NULL; } estado[s] = VISITADO; distancia[s] = 0; Encolar(Q, s); while !vacia(Q) do { // extraemos el nodo u de la cola Q y exploramos todos sus nodos adyacentes u = extraer(Q); for v ∈ adyacencia[u] do { if estado[v] == NO_VISITADO then { estado[v] = VISITADO; distancia[v] = distancia[u] + 1; padre[v] = u;

Encolar(Q, v); } }

}

}

Aplicaciones: •Buscar todos los componentes conexos en un grafo. •Buscar todos los nodos con un componente conexo •Buscar en camino mas corto entre dos vértices u y v (con y sin peso).

Árbol expandido minimal Un árbol expandido minimal (Minimal spaning tree) de un grafo es un subgrafo que forma un árbol, el cual pasa por todos los vértices del grafo y tiene un costo mínimo, etiquetado en cada una de las aristas. Cada grafo tiene su árbol recubridor mínimo.

Figura: Árbol espandido minimal. Algoritmos que encuentran el árbol mínimo: •Algoritmo de Prim •Algoritmo de Kruskal

Algoritmo de Prim El algoritmo de Prim es un algoritmo de la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo. Costo: Usando Fibonacci heap: O(E + V log V) Algoritmo: *Estructura de datos auxiliar: Q = Estructura de datos Cola de prioridad (se puede implementar con un heap) PRIM (Grafo G, nodo_fuente s) // inicializamos todos los nodos del grafo. La distancia la ponemos a infinito // y el padre de cada nodo a NULL for each u ∈ V[G] do distancia[u] = INFINITO padre[u] = NULL distancia[s]=0 Encolar(cola, V[G]) //encolamos todos los nodos del grafo while cola != 0 do // OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición de Cola de prioridad u = extraer_minimo(cola) for v ∈ adyacencia[u] do if ((v ∈ cola) && (distancia[v] > peso(u, v)) do padre[v] = u distancia[v] = peso(u, v) actualizar(cola,v);

Algoritmo de Kruskal Funciona de la siguiente manera:

• se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado • se crea un conjunto C que contenga a todas las aristas del grafo • mientras C es novacío • eliminar una arista de peso mínimo de C • si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol • en caso contrario, se desecha la arista Al acabar el algoritmo, el bosque tiene una sola componente, la cual forma un árbol de expansión mínimo del grafo.

Pseudocodigo: 1 function Kruskal(G) 2 for each vertex v in G do 3 Define an elementary cluster C(v) ← {v}. 4 Initialize a priority queue Q to contain all edges in G, using the weights as keys. 5 Define a tree T ← Ø //T will ultimately contain the edges of the MST 6 // n es el número total de vértices 7 while T has fewer than n-1 edges do 8 // edge u,v is the minimum weighted route from/to v 9 (u,v) ← Q.removeMin() 10 // previene ciclos en T. suma u,v solo si T no contiene una arista que una u y v. 11 // Nótese que el cluster contiene más de un vértice si una arista une un par de 12 // vértices que han sido añadidos al árbol. 13 Let C(v) be the cluster containing v, and let C(u) be the cluster containing u. 14 if C(v) ≠ C(u) then 15 Add edge (v,u) to T. 16 Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u). 17 return tree T

Costo: O(E Log V) m el número de aristas del grafo y n el número de vértices, el algoritmo de Kruskal muestra una complejidad O(m log m) o, equivalentemente, O(m log n), cuando se ejecuta sobre estructuras de datos simples. Los tiempos de ejecución son equivalentes porque: • m es a lo sumo n2 y log n2 = 2logn es O(log n). • ignorando los vértices aislados, los cuales forman su propia componente del árbol de expansión mínimo, n ≤ 2m, así que log n es O(log m). Se puede conseguir esta complejidad de la siguiente manera: primero se ordenan las aristas por su peso usando una ordenación por comparación (comparison sort) con una complejidad del orden de O(m log m); esto permite que el paso "eliminar una arista de peso mínimo de C" se ejecute en tiempo constante. Lo siguiente es usar una estructura de datos sobre conjuntos disjuntos (disjointset data structure) para controlar qué vértices están en qué componentes. Es necesario hacer orden de O(m) operaciones ya que por cada arista hay dos operaciones de búsqueda y posiblemente una unión de conjuntos. Incluso una estructura de datos sobre conjuntos disjuntos simple con uniones por rangos puede ejecutar las operaciones mencionadas en O(m log n). Por tanto, la complejidad

total es del orden de O(m log m) = O(m log n).

All pairs shortest path Buscar “Todos los pares de caminos más cortos” consiste en buscar la menor distancia entre cada par de nodos en un, posiblemente, grafo dirigido. Se conocen varios métodos para lograrlo, la siguiente lista muestra algunos métodos comunes: ◦Floyd-Warshall: es un elegante, y rápido algoritmo, de costo O(n³). Asume la ausencia de ciclos de peso negativo, aunque permite pesos negativos en las aristas. ◦Johnson's algoritmo: Es difícil de implementar, pero con mejor performance para grafo con pocas aristas. ◦Algoritmos para “single source path” pueden ser usados repetidamente, aunque hacer esto puede ser peor en costo o más difícil de optimizar.

Single-source shortest path Es el problema de encontrar un camino entre dos vértices (o nodos) tal que la suma de los pesos de sus aristas sea mínimo. Un ejemplo es buscar la vía más rápida desde una locación a otra en una carretera; en este caso, los vértices representan localidades y las aristas segmentos de carretera y los pesos, el tiempo que se requiere para viajar ese segmento. El problema es llamado aveces single-pair shortest path problem, para distinguirlo de las siguientes generalizaciones: ◦Single-source shortest path problem: Encontrar camino más corto desde un vértice origen 'v' a todos los demás en el grafo. ◦Single-destination shortest path problem: Encontrar camino más corto desde todos los vértices en el grafo hacia un vértice singular 'v' ◦All-pairs shortest path problem: Encontrar caminos mas cortos entre cada par de vértices v, v' en el grafo. Los algoritmos mas importantes que resuelven estos problemas son: ◦Dijkstra: Resuelve los problemas de “single-pair”, “single source” y “single-destination” shortest path problems. ◦Bellman-Ford: Resuelve el problema de “single source” si las aristas pueden tener pesos negativos. ◦Floyd-Warshall: Resuelve “All pairs shortest path”. ◦Johnson's : Resuelve “All pairs shortest path”, y puede ser mas rápido que Floyd-Warshall en grafos con pocos aristas. Usos: Mapas, Redes.

Dijkstra Resuelve “single-source path problem” para un grafo con pesos no negativos, produciendo un “árbol de caminos cortos”. Para un nodo raíz dado en el grafo, el algoritmo encuentra el camino con menor peso entre ese vértice y cada uno de los demás. Esto puede ser usado para encontrar el costo menor del camino de

vértices dados como origen y otro como destino,parando la ejecución una vez que esa camino a sido determinado. Costo: O( | E | + | V | log | V | ) con Fibonacci Heap. Algoritmo: Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos. 1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0. 2. Sea a = x (tomamos a como nodo actual). 3. Recorremos todos los nodos adyacentes de a menos los nodos marcados, llamaremos a estos vi. 4. Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a sumada a la distancia desde a hasta vi; esta se substituye con la segunda nombrada, esto es: si (Di > Da + d(a,vi)) entonces Di = Da + d(a,vi) 5. Marcamos como completo el nodo a. 6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados. Una vez terminado al algoritmo, D estará completamente lleno. dijkstra (Grafo G, nodo_fuente s) // inicializamos todos los nodos del grafo. La distancia de cada nodo es infinita // y los padres son NULL for u ∈ V[G] do distancia[u] = INFINITO padre[u] = NULL distancia[s] = 0 //encolamos el nodo_fuente s Encolar (cola, grafo) mientras cola no es vacía do // OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición // de Cola de prioridad u = extraer_mínimo(cola) for v ∈ adyacencia[u] do if u= source break if distancia[v] > distancia[u] + peso (u, v) do distancia[v] = distancia[u] + peso (u, v) padre[v] = u

Bellman-Ford El algoritmo de Bellman-Ford, genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos.

Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Algoritmo: Existen dos versiones: • Versión no optimizada para grafos con ciclos negativos, cuyo coste de tiempo es O(VE) • Versión optimizada para grafos con aristas de peso negativo, pero en el grafo no existen ciclos de coste negativo, cuyo coste de tiempo, es también O(VE). BellmanFord(Grafo G, nodo_origen s) // inicializamos el grafo. Ponemos distancias a INFINITO menos el nodo origen que // tiene distancia 0 for v ∈ V[G] do distancia[v]=INFINITO predecesor[v]=NIL distancia[s]=0 // relajamos cada arista del grafo tantas veces como número de nodos -1 haya en el grafo for i=1 to |V[G]-1| do for (u,v) ∈ E[G] do if distancia[v]>distancia[u] + peso(u,v) then distancia[v] = distancia[u] + peso (u,v) predecesor[v] = u // comprobamos si hay ciclos negativo for (u,v) ∈ E[G] do if distancia[v] > distancia[u] + peso(u,v) then print ("Hay ciclo negativo") return FALSE return TRUE BellmanFord_Optimizado(Grafo G, nodo_origen s) // inicializamos el grafo. Ponemos distancias a INFINITO menos el nodo origen que // tiene distancia 0. Para ello lo hacemos recorriéndonos todos los vértices del grafo for v ∈ V[G] do distancia[v]=INFINITO padre[v]=NIL distancia[s]=0 encolar(s, Q) en_cola[s]=TRUE mientras Q!=0 then u = extraer(Q) en_cola[u]=FALSE // relajamos las aristas for v ∈ ady[u] do if distancia[v]>distancia[u] + peso(u,v) then distancia[v] = distancia[u] + peso (u,v) padre[v] = u if en_cola[v]==FALSE then encolar(v, Q) en_cola[v]=TRUE

Algoritmo de Johnson Es una forma de encontrar el camino más corto entre todos los pares de vértices de un grafo dirigido

disperso. Permite que las aristas tengan pesos negativos, si bien no permite ciclos de peso negativo. Funciona utilizando el algoritmo de Bellman-Ford para hacer una transformación en el grafo inicial que elimina todas las aristas de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo transformado. La complejidad temporal de este algoritmo, usando montículos de Fibonacci en la implementación del algoritmo de Dijkstra, es de O(V^2log V + VE): el algoritmo usa un tiempo de O(VE) para la fase Bellman-Ford del algoritmo, y O(V log V + E) para cada una de las V instancias realizadas del algoritmo de Dijkstra. Entonces, cuando el grafo es disperso el tiempo total del algoritmo puede ser menor que el algoritmo de Floyd-Warshall, que resuelve el mismo problema en un tiempo de O(V^3). El algoritmo de Johnson consiste en los siguientes pasos: 1. Primero se añade un nuevo nodo q al grafo, conectado a cada uno de los nodos del grafo por una arista de peso cero. 2. En segundo lugar, se utiliza el algoritmo de Bellman-Ford, empezando por el nuevo vértice q, se determina para cada vértice v el peso mínimo h(v) del camino de q a v. Si en este paso se detecta un ciclo negativo, el algoritmo concluye. 3. Seguidamente, a las aristas del grafo original se les cambia el peso usando los valores calculados por el algoritmo de Bellman-Ford: una arista de u a v con tamaño w(u,v), da el nuevo tamaño w(u,v) + h(u) – h(v) 4. Por último, para cada nodo s se usa el algoritmo de Dijkstra para determinar el camino más corto entre s y los otros nodos, usando el grafo con pesos modificados. En el grafo con pesos modificados, todos los caminos entre un par de nodos s y t tienen la misma cantidad h(s) – h(t) añadida a cada uno de ellos, así que un camino que sea el más corto en el grafo original también es el camino más corto en el grafo modificado y viceversa. Sin embargo, debido al modo en el que los valores h(v) son computados, todos los pesos modificados de las aristas son no negativos, asegurando entonces la optimalidad de los caminos encontrados por el algoritmo de Dijkstra. Las distancias en el grafo original pueden ser calculadas a partir de las distancias calculadas por el algoritmo de Dijkstra en el grafo modificado invirtiendo la transformación realizada en el grafo. Tipos Arista = REGISTRO o : NATURAL d : NATURAL peso : INT sig : NATURAL FIN LAristas = PUNTERO A Arista TGrafo = ARRAY [1..N] DE LAristas THv = ARRAY [1..N] DE ENTERO TVector = ARRAY [1..N] DE ENTERO TMatriz = ARRAY [1..N] DE TVector //suponemos ig>1 PROC Johnson (↓grafo: TGrafo; ↓ig: NATURAL; ↑ distancias: TMatriz ; ↑ previos: TMatriz) VARIABLES i : NATURAL p : LAristas min_caminos : THv aux_dist, aux_prev : TVector INICIO grafo[ig] ← nueva_arista(ig,1,0,NULO)

FIN

inc(ig) p ← grafo[ig] PARA i ← 2 HASTA ig-2 HACER p^.sig ← nueva_arista(ig,i,0,NULO) p ← p^.sig FIN BellmanFord(grafo,ig, min_caminos) PARA i ← 1 HASTA ig-1 HACER p ← grafo[i] MIENTRAS (p != NULO) HACER p^.peso ← p^.peso + min_caminos[p^.o] - min_caminos[p^.d] p ← p^.sig FIN FIN PARA i ← 1 HASTA ig-2 HACER Dijkstra(grafo,i, aux_dist,aux_prev) // devuelve los caminos mínimos desde el último nodo // a todos los demás previos[i] ← aux_prev; CalcularDistancias(grafo, previos, aux_dist,distancias); // este algoritmo realiza la transformación inversa a la // que habíamos hecho antes sobre los pesos, para obtener // las distancias reales. FIN

Las etapas del algoritmo de Johnson están descritas en la siguiente ilustración:

En la imagen de la izquierda tiene dos aristas negativas y no contiene ciclos negativos. En la segunda imagen se muestra el nuevo vértice q con peso 0 hacia todos los nodos. En la tercera imagen, se muestra el árbol de caminos mínimos calculado con el algoritmo de Bellman-Ford con q como vértice inicial, y los valores h(v) calculados para cada otro nodo como la longitud del camino más corto entre q y ese nodo. A modo de ilustración, en dicha imagen solo aparecen los caminos que se tomarían para determinar cada valor h(v). Nótese que todos estos valores h(v) no son positivos, porque q tiene una arista de unión con cada nodo de peso 0, y por tanto el camino más corto no puede ser mayor que ese valor. En la parte derecha se muestra el grafo modificado, hecho reemplazando el peso de cada arista w(u,v) por w(u,v) + h(u) – h(v). En este grafo modificado, todos los pesos de las aristas son positivos y el camino más corto entre dos nodos cualesquiera usa la misma secuencia de aristas que en el camino más corto entre los mismos dos nodos en el grafo original. El algoritmo concluye aplicando el algoritmo de Dijkstra para cada uno de los cuatro nodos originales en el grafo modificado (cuarta imagen).

Floyd-Warshall Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices (All-pairs shortest path) en una única ejecución. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica.

Algoritmo: 1 /* Suponemos que la función pesoArista devuelve el coste del camino que va de i a j 2 (infinito si no existe). 3 También suponemos que n es el número de vértices y pesoArista(i,i) = 0 4 */ 5 6 int camino[][]; 7 /* Una matriz bidimensional. En cada paso del algoritmo, camino[i][j] es el camino mínimo 8 de i hasta j usando valores intermedios de (1..k-1). Cada camino[i] 9 [j] es inicializado a pesoArista(i,j) 10 */ 11 12 procedimiento FloydWarshall () 13 para k: = 0 hasta n − 1 15 para i: = 0 hasta n -1 16 para j: 0 hasta n -1 17 d[i][j] = mín ( d[i][j], d[i][k] + d[k][j]);

Respecto a ciclos negativos: Para que haya coherencia numérica, Floyd-Warshall supone que no hay ciclos negativos (de hecho, entre cualquier pareja de vértices que forme parte de un ciclo negativo, el camino mínimo no está bien definido porque el camino puede ser infinitamente pequeño). No obstante, si hay ciclos negativos, Floyd-Warshall puede ser usado para detectarlos. Si ejecutamos el algoritmo una vez más, algunos caminos pueden decrementarse pero no garantiza que, entre todos los vértices, caminos entre los cuales puedan ser infinitamente pequeños, el camino se reduzca. Si los números de la diagonal de la matriz de caminos son negativos , es condición necesaria y suficiente para que este vértice pertenezca a un ciclo negativo. Ejecución: Hallar el camino mínimo desde el vértice 3 hasta 4 en el grafo con la siguiente matriz de distancias:

Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteración fijamos un vértice intermedio. 1ª Iteración: nodo intermedio = 1 La matriz es simétrica, por lo que solamente hará falta calcular el triangulo superior de las distancias. d23 = min(d23, d21 + d13) = 8 d24 = min(d24, d21 + d14) = 4 d25 = min(d25, d21 + d15) = 9 d26 = min(d26, d21 + d16) = d34 = min(d34, d31 + d14) = 6 d35 = min(d35, d31 + d15) = 7 d36 = min(d36, d31 + d16) = 1 d45 = min(d45, d41 + d15) = d46 = min(d46, d41 + d16) = 4 d56 = min(d56, d51 + d16) = La matriz de distancia después de esta iteración es:

2ª Iteración: nodo intermedio = 2 d13 = min(d13, d12 + d23) = 5 d14 = min(d14, d12 + d24) = 1 d15 = min(d15, d12 + d25) = 12 d16 = min(d16, d12 + d26) =

d34 = min(d34, d32 + d24) = 6 d35 = min(d35, d32 + d25) = 7 d36 = min(d36, d32 + d26) = 1 d45 = min(d45, d42 + d25) = 13 d46 = min(d46, d42 + d26) = 4 d56 = min(d56, d52 + d26) = La matriz de distancia después de esta iteración es:

3ª Iteración: nodo intermedio = 3 d12 = min(d12, d13 + d32) = 3 d14 = min(d14, d13 + d34) = 1 d15 = min(d15, d13 + d35) = 12 d16 = min(d16, d13 + d36) = 6 d24 = min(d24, d23 + d34) = 4 d25 = min(d25, d23 + d35) = 9 d26 = min(d26, d23 + d36) = 9 d45 = min(d45, d43 + d35) = 13 d46 = min(d46, d43 + d36) = 4 d56 = min(d56, d53 + d36) = 8 La matriz de distancia después de esta iteración es:

4ª Iteración: nodo intermedio = 4

d12 = min(d12, d14 + d42) = 3 d13 = min(d13, d14 + d43) = 5 d15 = min(d15, d14 + d45) = 12 d16 = min(d16, d14 + d46) = 5 d23 = min(d23, d24 + d43) = 8 d25 = min(d25, d24 + d45) = 9 d26 = min(d26, d24 + d46) = 8 d35 = min(d35, d34 + d45) = 7 d36 = min(d36, d34 + d46) = 1 d56 = min(d56, d54 + d46) = 8 La matriz de distancia después de esta iteración es:

5ª Iteración: nodo intermedio = 5 d12 = min(d12, d15 + d52) = 3 d13 = min(d13, d15 + d53) = 5 d14 = min(d14, d15 + d54) = 1 d16 = min(d16, d15 + d56) = 5 d23 = min(d23, d25 + d53) = 8 d24 = min(d24, d25 + d54) = 4 d26 = min(d26, d25 + d56) = 8 d34 = min(d34, d35 + d54) = 6 d36 = min(d36, d35 + d56) = 1 d46 = min(d46, d45 + d56) = 4 La matriz de distancia después de esta iteración es:

6ª Iteración: nodo intermedio = 6 d12 = min(d12, d16 + d62) = 3 d13 = min(d13, d16 + d63) = 5 d14 = min(d14, d16 + d64) = 1 d15 = min(d15, d16 + d65) = 12 d23 = min(d23, d26 + d63) = 8 d24 = min(d24, d26 + d64) = 4 d25 = min(d25, d26 + d65) = 9 d34 = min(d34, d36 + d64) = 5 d35 = min(d35, d36 + d65) = 7 d45 = min(d45, d46 + d65) = 12 La matriz de distancia después de esta iteración es:

Ya se han hecho todas las iteraciones posibles. Por tanto, el camino mínimo entre 2 vértices cualesquiera del grafo será el obtenido en la matriz final. En este caso, el camino mínimo entre 3 y 4 vale 5.

Heaps Es una estructura de Árbol con información perteneciente a un conjunto ordenado. Los montículos tienen la característica de que cada nodo padre tiene un valor mayor que el de todos sus nodos hijos. Un árbol cumple la condición de montículo si satisface dicha condición y además es un árbol binario completo.Un árbol binario es completo cuando todos los niveles están llenos, con la excepción del último que puede quedar exento de dicho cumplimiento. Ésta es la única restricción en los montículos. Ella implica que el mayor elemento (o el menor, dependiendo de la relación de orden escogida) está siempre en el nodo raíz. Debido a esto, los montículos se utilizan para implementar colas de prioridad, por la razón de que en una cola siempre se consulta el elemento de mayor valor, y esto conlleva la ventaja de que en los montículos dicho elemento está en la raíz. Otra ventaja que poseen los montículos es que su implementación usando

arrays es muy eficaz, por la sencillez de su codificación y liberación de memoria, ya que no hace falta utilizar punteros.No sólo existen montículos ordenados con el elemento de la raíz mayor que el de sus hijos, sino también en caso contrario que la raíz sea menor que sus progenitores. Todo depende de la ordenación con la que nos interese programar el montículo, que debe ser parámetro de los algoritmos de construcción y de manipulación de dicho montículo. La eficiencia de las operaciones en los montículos es crucial en diversos algoritmos de recorrido de grafos y de ordenamiento (Heapsort).

Heap de Fibonacci * ver documento anexo. Un Heap de Fibonacci es una colección de árboles que satisfacen la propiedad de Min-Heap, es decir, la clave de un hijo es siempre mayor o igual que la de su padre. Esto implica que la clave mínima está siempre en la raíz. Comparado con los Heaps binomiales, la estructura de un heap de Fibonacci es más flexible. Los árboles no tienen una forma predefinida y en un caso extremo el heap puede tener cada elemento en un árbol separado o en un único árbol de profundidad n. Esta flexibilidad permite que algunas operaciones puedan ser ejecutadas de una manera ‘perezosa’, posponiendo el trabajo para operaciones posteriores. Por ejemplo, la unión de dos Heaps se hace simplemente concatenando las dos listas de árboles, y la operación Decrementar clave a veces corta un nodo de su padre y forma un nuevo árbol. Sin embargo, se debe introducir algún orden para conseguir el tiempo de ejecución deseado. En concreto, el grado de los nodos(el número de hijos) se tiene que mantener bajo: cada nodo tiene un grado máximo de O(logn) y la talla de un subárbol cuya raíz tiene grado k es por lo menos Fk+2 , donde Fk es un número de Fibonacci (por eso el nombre que se les da a este tipo de heap. Esto se consigue con la regla de que podemos cortar como mucho un hijo de cada nodo no raíz. Cuando es cortado un segundo hijo, el nodo también necesita ser cortado de su padre y se convierte en la raíz de un nuevo árbol. El número de árboles se decrementa en la operación Borrar mínimo, donde los árboles están unidos entre sí. Como resultado de esta estructura, algunas operaciones pueden llevar mucho tiempo mientras que otras se hacen muy deprisa. En el análisis del coste de ejecución amortizado pretendemos que las operaciones muy rápidas tarden un poco más de lo que tardan. Este tiempo extra se resta después al tiempo de ejecución de operaciones más lentas. La cantidad de tiempo ahorrada para un uso posterior es medida por una función potencial. Esta función es:

Object 1

Donde t es el número de árboles en el Heap de Fibonacci, y m es el número de nodos marcados. Un nodo está marcado si al menos uno de sus hijos se cortó desde que el nodo se fue hecho hijo de otro nodo (todas las raíces están desmarcadas). Además, la raíz de cada árbol en un Heap tiene una unidad de tiempo almacenada. Esta unidad de tiempo puede ser usada más tarde para unir este árbol a otro con coste amortizado 0. Cada nodo marcado también tiene dos unidades de tiempo almacenadas. Una puede ser usada para cortar el nodo de su padre. Si esto sucede, el nodo se convierte en una raíz y la segunda unidad de tiempo se mantendrá almacenada como en cualquier otra raíz.