Estrategia GreedyEl mtodo codicioso consiste en tomar sucesivamente, las decisiones de modo que cada decisin individual sea la mejor de acuerdo con algn criterio limitado "a corto plazo" cuya evaluacin no sea demasiado costosa. Una vez tomada una decisin, no se podr revertir, ni siquiera si ms adelante se hace obvio que no fue una buena decisin. Por esta razn, los mtodos codiciosos no necesariamente hallan la solucin ptima en muchos problemas. No obstante, en el caso de los problemas que se estudiaran en este captulo, 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 decisin que aparentemente es la mejor, sin considerar o lamentar futuras consecuencias. Generalmente, esta idea es pensada como escoger algn 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 solucin 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 ms complicados que requieren de otra estrategia para generar "la" respuesta correcta. En general la estrategia Greedy trabaja en etapas "Top-Down" realizando una eleccin greedy despus de la otra. En resumen, la estrategia Greedy consiste de dos partes: 1. Subestructura Optimal 2. Partir con eleccin de ptimos locales y continuar haciendo elecciones localmente optimales, hasta que la solucin es encontrada. Problemas Asociados a esta tcnica : 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 ms pequeo 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 nmero de billetes y monedas es el mnimo. (Problema de Planificacin de Tareas) Dado los trabajos t 1, t 2, ... t n, con tiempos t1, t2, ... tn y un solo procesador. Cul es la mejor forma de planificar esos trabajos a fin de minimizar el tiempo medio de terminacin? (Cdigo de Huffman) en la compresin de archivos. Un cdigo de longitud fija de un alfabeto A= { a1 , a2 , ..., am } con m-letras es una expresin 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 algn conjunto de smbolos. El conjunto C = { ci,1 ci,2 ...ci,n , tal que, i= 1, ...m, es llamado cdigo de longitud fija de longitud n, y cada ci,1 ci,2 ...ci,,n es llamado cdigo. Veamos con cierto detalle, como funciona esta estrategia en la resolucin 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 representacin elegida. En particular, los tiempos de ejecucin variarn en funcin del nmero de vrtices y el de aristas, por lo que la utilizacin de una representacin 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 vrtices 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 ms utilizadas de representacin de los grafos son: a. Representacin por matriz de adyacencia b. Representacin por listas de adyacencias La matriz de adyacencia es la forma ms comn de representacin y la ms directa. Consiste en una tabla de tamao nxn, en que la que aij tendr como valor 1 si existe una arista del vrtice i al vrtice 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 nmero 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 vrtices del grafo y para cada vrtice de una lista de sus vrtices vecinos. Ejemplos:

Directed acyclic graph (DAG)Es un grafo dirigido con siglos no dirigidos, que es, para algn vrtice v, no hay caminos dirigidos en que v sea el inicio y final. Orden topolgico: Orden topolgico de un DAG G=(V,E) es un orden lineal de todos los vrtices 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 ejecucin sin conflictos. Grficamente se trata de poner todos los nodos en una lnea de manera que slo haya arcos hacia delante. Algoritmo: Topological_Orden(G) Llamar a DFS(G) para calcular el tiempo de trmino f[v] para cada vrtice. Insertar cada nodo en una lista enlazada segn su orden de trmino. Retornar la lista enlazada. Costo: O(V + E),

Bsqueda en profundidadUna Bsqueda en profundidad (en ingls 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 ms 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

Clasificacin de las aristas o ejes y parentizacin

Otra propiedad interesante de depth-first search es que puede servir para clasificar las aristas del grafo G=(V,E). Esa clasificacin de ejes puede ser usada para recoger importante informacin acerca del grafo. Por ejemplo, un grafo dirigido es acclico 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 vrtice u con un vrtice v ancestro en el depth-first tree. Forward edges: Son aquellas aristas que conectan un vrtice u con un vrtice v descendiente en el depth-first tree. Cross edges: Son todos las dems aristas. Ellos pueden ir desde vrtices en el mismo depthfirst tree, a lo largo de un vrtice que no es ancestro de otro, o pueden ir de vrtices de diferentes depth-first trees.

a) Resultado de DFS. b) Lema de parentizacin. c)Tipos de aristas en el DFS.

Bsqueda en anchuraEs un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre rboles). Intuitivamente, se comienza en la raz (eligiendo algn nodo como elemento raz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuacin 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 bsqueda sin informacin, que expande y examina todos los nodos de un rbol sistemticamente para buscar una solucin. El algoritmo no usa ninguna estrategia heurstica. Costo: O( | V | + | E | ) = O(bd) Procedimiento: Dado un vrtice fuente s, Breadth-first search sistemticamente explora los vrtices de G para descubrir todos los vrtices alcanzables desde s. Calcula la distancia (menor nmero de vrtices) desde s a todos los vrtices alcanzables. Despus produce un rbol BF con raz en s y que contiene a todos los vrtices alcanzables. El camino desde s a cada vrtice en este recorrido contiene el mnimo nmero de vrtices. Es el camino ms corto medido en nmero de vrtices. Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a los nodos de distancia k, slo tras haber llegado a todos los nodos a distancia k-1. Algoritmo:BFS(grafo G, nodo_fuente s) { // recorremos todos los vrtices del grafo inicializndolos 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 vrtices u y v (con y sin peso).

rbol expandido minimalUn rbol expandido minimal (Minimal spaning tree) de un grafo es un subgrafo que forma un rbol, el cual pasa por todos los vrtices del grafo y tiene un costo mnimo, etiquetado en cada una de las aristas. Cada grafo tiene su rbol recubridor mnimo.

Figura: rbol espandido minimal. Algoritmos que encuentran el rbol mnimo: Algoritmo de Prim Algoritmo de Kruskal

Algoritmo de PrimEl algoritmo de Prim es un algoritmo de la teora de los grafos para encontrar un rbol recubridor mnimo en un grafo conexo, no dirigido y cuyas aristas estn etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un rbol con todos los vrtices, donde el peso total de todas las aristas en el rbol es el mnimo posible. Si el grafo no es conexo, entonces el algoritmo encontrar el rbol recubridor mnimo 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 mnima y se conserva la condicin 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 KruskalFunciona de la siguiente manera:

se crea un bosque B (un conjunto de rboles), donde cada vrtice del grafo es un rbol separado se crea un conjunto C que contenga a todas las aristas del grafo mientras C es novaco eliminar una arista de peso mnimo de C si esa arista conecta dos rboles diferentes se aade 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 expansin mnimo 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 nmero total de vrtices 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 // Ntese que el cluster contiene ms de un vrtice si una arista une un par de 12 // vrtices que han sido aadidos 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 nmero de aristas del grafo y n el nmero de vrtices, 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 ejecucin son equivalentes porque: m es a lo sumo n2 y log n2 = 2logn es O(log n). ignorando los vrtices aislados, los cuales forman su propia componente del rbol de expansin mnimo, 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 ordenacin por comparacin (comparison sort) con una complejidad del orden de O(m log m); esto permite que el paso "eliminar una arista de peso mnimo de C" se ejecute en tiempo constante. Lo siguiente es usar una estructura de datos sobre conjuntos disjuntos (disjointset data structure) para controlar qu vrtices estn en qu componentes. Es necesario hacer orden de O(m) operaciones ya que por cada arista hay dos operaciones de bsqueda y posiblemente una unin 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 pathBuscar Todos los pares de caminos ms cortos consiste en buscar la menor distancia entre cada par de nodos en un, posiblemente, grafo dirigido. Se conocen varios mtodos para lograrlo, la siguiente lista muestra algunos mtodos comunes: Floyd-Warshall: es un elegante, y rpido algoritmo, de costo O(n). Asume la ausencia de ciclos de peso negativo, aunque permite pesos negativos en las aristas. Johnson's algoritmo: Es difcil 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 ms difcil de optimizar.

Single-source shortest pathEs el problema de encontrar un camino entre dos vrtices (o nodos) tal que la suma de los pesos de sus aristas sea mnimo. Un ejemplo es buscar la va ms rpida desde una locacin a otra en una carretera; en este caso, los vrtices 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 ms corto desde un vrtice origen 'v' a todos los dems en el grafo. Single-destination shortest path problem: Encontrar camino ms corto desde todos los vrtices en el grafo hacia un vrtice singular 'v' All-pairs shortest path problem: Encontrar caminos mas cortos entre cada par de vrtices 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 rpido que Floyd-Warshall en grafos con pocos aristas. Usos: Mapas, Redes.

DijkstraResuelve single-source path problem para un grafo con pesos no negativos, produciendo un rbol de caminos cortos. Para un nodo raz dado en el grafo, el algoritmo encuentra el camino con menor peso entre ese vrtice y cada uno de los dems. Esto puede ser usado para encontrar el costo menor del camino de

vrtices dados como origen y otro como destino,parando la ejecucin 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 tamao 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 sera 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 prximo 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 vaca do // OJO: Se extrae el nodo que tiene distancia mnima y se conserva la condicin // de Cola de prioridad u = extraer_mnimo(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-FordEl algoritmo de Bellman-Ford, genera el camino ms 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: Versin no optimizada para grafos con ciclos negativos, cuyo coste de tiempo es O(VE) Versin optimizada para grafos con aristas de peso negativo, pero en el grafo no existen ciclos de coste negativo, cuyo coste de tiempo, es tambin 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 nmero 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 recorrindonos todos los vrtices 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 JohnsonEs una forma de encontrar el camino ms corto entre todos los pares de vrtices 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 transformacin 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 montculos de Fibonacci en la implementacin 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 aade 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 vrtice q, se determina para cada vrtice v el peso mnimo 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 tamao w(u,v), da el nuevo tamao w(u,v) + h(u) h(v) 4. Por ltimo, para cada nodo s se usa el algoritmo de Dijkstra para determinar el camino ms 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) aadida a cada uno de ellos, as que un camino que sea el ms corto en el grafo original tambin es el camino ms 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 transformacin 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 mnimos desde el ltimo nodo // a todos los dems previos[i] aux_prev; CalcularDistancias(grafo, previos, aux_dist,distancias); // este algoritmo realiza la transformacin inversa a la // que habamos hecho antes sobre los pesos, para obtener // las distancias reales. FIN

Las etapas del algoritmo de Johnson estn descritas en la siguiente ilustracin:

En la imagen de la izquierda tiene dos aristas negativas y no contiene ciclos negativos. En la segunda imagen se muestra el nuevo vrtice q con peso 0 hacia todos los nodos. En la tercera imagen, se muestra el rbol de caminos mnimos calculado con el algoritmo de Bellman-Ford con q como vrtice inicial, y los valores h(v) calculados para cada otro nodo como la longitud del camino ms corto entre q y ese nodo. A modo de ilustracin, en dicha imagen solo aparecen los caminos que se tomaran para determinar cada valor h(v). Ntese que todos estos valores h(v) no son positivos, porque q tiene una arista de unin con cada nodo de peso 0, y por tanto el camino ms 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 ms corto entre dos nodos cualesquiera usa la misma secuencia de aristas que en el camino ms 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-WarshallEs un algoritmo de anlisis sobre grafos para encontrar el camino mnimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vrtices (All-pairs shortest path) en una nica ejecucin. El algoritmo de Floyd-Warshall es un ejemplo de programacin dinmica.

Algoritmo:1 /* Suponemos que la funcin pesoArista devuelve el coste del camino que va de i a j 2 (infinito si no existe). 3 Tambin suponemos que n es el nmero de vrtices 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 mnimo 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] = mn ( d[i][j], d[i][k] + d[k][j]);

Respecto a ciclos negativos: Para que haya coherencia numrica, Floyd-Warshall supone que no hay ciclos negativos (de hecho, entre cualquier pareja de vrtices que forme parte de un ciclo negativo, el camino mnimo no est bien definido porque el camino puede ser infinitamente pequeo). No obstante, si hay ciclos negativos, Floyd-Warshall puede ser usado para detectarlos. Si ejecutamos el algoritmo una vez ms, algunos caminos pueden decrementarse pero no garantiza que, entre todos los vrtices, caminos entre los cuales puedan ser infinitamente pequeos, el camino se reduzca. Si los nmeros de la diagonal de la matriz de caminos son negativos , es condicin necesaria y suficiente para que este vrtice pertenezca a un ciclo negativo. Ejecucin: Hallar el camino mnimo desde el vrtice 3 hasta 4 en el grafo con la siguiente matriz de distancias:

Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteracin fijamos un vrtice intermedio. 1 Iteracin: nodo intermedio = 1 La matriz es simtrica, 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 despus de esta iteracin es:

2 Iteracin: 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 despus de esta iteracin es:

3 Iteracin: 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 despus de esta iteracin es:

4 Iteracin: 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 despus de esta iteracin es:

5 Iteracin: 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 despus de esta iteracin es:

6 Iteracin: 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 despus de esta iteracin es:

Ya se han hecho todas las iteraciones posibles. Por tanto, el camino mnimo entre 2 vrtices cualesquiera del grafo ser el obtenido en la matriz final. En este caso, el camino mnimo entre 3 y 4 vale 5.

HeapsEs una estructura de rbol con informacin perteneciente a un conjunto ordenado. Los montculos tienen la caracterstica de que cada nodo padre tiene un valor mayor que el de todos sus nodos hijos. Un rbol cumple la condicin de montculo si satisface dicha condicin y adems es un rbol binario completo.Un rbol binario es completo cuando todos los niveles estn llenos, con la excepcin del ltimo que puede quedar exento de dicho cumplimiento. sta es la nica restriccin en los montculos. Ella implica que el mayor elemento (o el menor, dependiendo de la relacin de orden escogida) est siempre en el nodo raz. Debido a esto, los montculos se utilizan para implementar colas de prioridad, por la razn de que en una cola siempre se consulta el elemento de mayor valor, y esto conlleva la ventaja de que en los montculos dicho elemento est en la raz. Otra ventaja que poseen los montculos es que su implementacin usando

arrays es muy eficaz, por la sencillez de su codificacin y liberacin de memoria, ya que no hace falta utilizar punteros.No slo existen montculos ordenados con el elemento de la raz mayor que el de sus hijos, sino tambin en caso contrario que la raz sea menor que sus progenitores. Todo depende de la ordenacin con la que nos interese programar el montculo, que debe ser parmetro de los algoritmos de construccin y de manipulacin de dicho montculo. La eficiencia de las operaciones en los montculos 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 coleccin 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 mnima est siempre en la raz. Comparado con los Heaps binomiales, la estructura de un heap de Fibonacci es ms 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 unin de dos Heaps se hace simplemente concatenando las dos listas de rboles, y la operacin Decrementar clave a veces corta un nodo de su padre y forma un nuevo rbol. Sin embargo, se debe introducir algn orden para conseguir el tiempo de ejecucin deseado. En concreto, el grado de los nodos(el nmero de hijos) se tiene que mantener bajo: cada nodo tiene un grado mximo de O(logn) y la talla de un subrbol cuya raz tiene grado k es por lo menos Fk+2 , donde Fk es un nmero 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 raz. Cuando es cortado un segundo hijo, el nodo tambin necesita ser cortado de su padre y se convierte en la raz de un nuevo rbol. El nmero de rboles se decrementa en la operacin Borrar mnimo, donde los rboles estn unidos entre s. Como resultado de esta estructura, algunas operaciones pueden llevar mucho tiempo mientras que otras se hacen muy deprisa. En el anlisis del coste de ejecucin amortizado pretendemos que las operaciones muy rpidas tarden un poco ms de lo que tardan. Este tiempo extra se resta despus al tiempo de ejecucin de operaciones ms lentas. La cantidad de tiempo ahorrada para un uso posterior es medida por una funcin potencial. Esta funcin es:

Object1

Donde t es el nmero de rboles en el Heap de Fibonacci, y m es el nmero 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 races estn desmarcadas). Adems, la raz de cada rbol en un Heap tiene una unidad de tiempo almacenada. Esta unidad de tiempo puede ser usada ms tarde para unir este rbol a otro con coste amortizado 0. Cada nodo marcado tambin 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 raz y la segunda unidad de tiempo se mantendr almacenada como en cualquier otra raz.