La ejecución del algoritmo termina en este momento porque z V(T). La trayectoria más corta de a a z tiene longitud L(z) 14. Siguiendo los pasos en ...

La ejecución del algoritmo termina en este momento porque z V(T). La trayectoria más corta de a a z tiene longitud L(z) 14. Siguiendo los pasos en una tabla es una forma conveniente de mostrar la acción de algoritmo de Dijkstra. La tabla 10.7.1 hace esto para el grafo del ejemplo 10.7.5. Tabla 10.7.1 Paso V T E T F L a L b L c L d L e L z 0 a a 0 1 a b c 0 3 4 2 a b a b c d e 0 3 4 9 8 3 a b c a b a c d e 0 3 4 9 5 4 a b c e a b a c c e d z 0 3 4 7 5 17 5 a b c e d a b a c c e e d z 0 3 4 7 5 14 6 a b c e d z a b a c c e e d e z Es claro que el algoritmo de Dijkstra mantiene agregar vértices a I hasta se que han agregado a z. La demostración del teorema siguiente muestra que cuando termina el algoritmo, la etiqueta z recorre la longitud de la trayectoria más corta de a. Teorema 10.7.4 Corrección del algoritmo de Dijkstra Cuando un grafo conexo simple, con un peso positivo para cada arista es la entrada al algoritmo de Dijkstra con vértice inicial a y vértice final z, la salida es la longitud de una trayectoria más corta de a a z. Demostración: Sea G un grafo conexo, pesado sin bucles o aristas paralelas y con un peso positivo para cada arista. Sea T el grafo creado por el algoritmo de Dijkstra y para cada vértice u en G, sea L(u) la etiqueta dada por el algoritmo al vértice u. Para cada entero n 0, que la propiedad P(n) sea la frase Después de la enésima iteración del bucle while en el algoritmo de Dijkstra, 1) T es un árbol y 2) para cada vértice en T, P(n) L( ) es la longitud de una trayectoria más corta en G de a a . Mostraremos por inducción matemática que P(n) es verdadera para todos los enteros n de 0 a la terminación del algoritmo. Demostración de que P(0) es verdadero: Cuando n 0, el grafo T es un árbol porque se define que consta sólo del vértice a y sin extremos. Además, L(a) es la longitud de la trayectoria más corta de a a a ya que el valor inicial de L(a) es 0. Demostración de que para todos los enteros k 0, si P(k) es verdadero entonces P(k 1) es también verdadero: Sea k cualquier entero con k 0 y suponga que Después de la k-ésima iteración del bucle while en el algoritmo P(k) de Dijkstra, 1) T es un árbol y 2) para cada vértice en T, L( ) es hipótesis la longitud de la trayectoria más corta en G de a a . de inducción Debemos demostrar que Después de la (k l)ésima iteración del bucle while en el algoritmo de Dijkstra, 1) T es un árbol y 2) para cada vértice en T, P(k 1) L( ) es la longitud de la trayectoria más corta en G de a a . continúa en la página 714 714 Capítulo 10 Grafos y árboles Así que suponga que después de la (k l)ésima iteración del bucle while en el algoritmo de Dikjstra, el vértice y la arista {x, } se han agregado a T, donde x está en V(T). Claramente el nuevo valor de T es un árbol porque agregar un vértice nuevo y arista a un árbol no crea un circuito y desconecta el árbol. Por hipótesis de inducción para cada vértice y en el árbol antes de la adición de , L(y) es la longitud de una trayectoria más corta de a a y. Así queda sólo mostrar que L( ) es la longitud de una trayectoria más corta de a a . Ahora, de acuerdo con el algoritmo, el valor final de L( ) L(x) (x, ). Considere cualquier trayectoria más corta de a a y {s, t} la primer arista en esta trayectoria que sale de T, donde s V(T) y t V(T). Este caso se muestra a continuación. a s x v t Sea LSP(a, ) la longitud de la trayectoria más corta de a a y sea LSP(a, s) la longitud de la trayectoria más corta de a a s. Observe que L S P(a, v) ≥ L S P(a, s) + w(s, t) ≥ L(s) + w(s, t) ≥ L(x) + w(x, v) ya que la trayectoria de t a tiene longitud 0 por hipótesis de inducción porque s es un vértice en T t está en la franja del árbol y así si L(s) (s, t) eran menores que L(x) (x, ) entonces se tendría que agregar t en lugar de . Por otro lado L(x) + w(x, v) ≥ L S P(a, v) ya que L(x) (x, ) es la longitud de una trayectoria de a a y que es mayor o igual a la longitud de la trayectoria más corta de a a . Se deduce que L S P(a, v) = L(x) + w(x, v), y puesto que L(v) = L(x) + w(x, v), L( ) es la longitud de la trayectoria más corta de a a . Esto completa la demostración por inducción matemática. El algoritmo termina tan pronto como z esté en T y ya hemos demostrado que la marca de cada vértice en el árbol indica la longitud de la trayectoria más corta de a, entonces, en particular, L(z) es la longitud de una trayectoria más corta de a a z. Autoexamen 1. Un árbol expandido para un grafo G es . 2. Un grafo pesado es un grafo para la que y el peso total del grafo es . 3. Un árbol expandido mínimo para un grafo conexo pesada es . 4. En el algoritmo de Kruskal, las aristas de un grafo conexo, pesado se examinan uno por uno en orden de comenzando con . 5. En el algoritmo de Prim, un árbol expandido mínimo se construye por expansión hacia el exterior de un en una sucesión de . 6. En el algoritmo de Dijkstra, un vértice está en la franja si es un vértice en el árbol que se está construyendo. 7. En cada etapa del algoritmo de Dijkstra, el vértice que se agrega al árbol es un vértice en la franja cuya etiqueta es un . Conjunto de ejercicios 10.7 Encuentre todos los posibles árboles expandidos para cada uno de los grafos 1 y 2. 1. a b d c 2. 0 1 3 2 Encuentre un árbol expandido para cada una de los grafos en los ejercicios 3 y 4. 3. a g b d c e f 4. z r s t u y x Utilice el algoritmo de Kruskal para encontrar un árbol expandido mínimo para cada una de los grafos en los ejercicios 5 y 6. Indique el orden en que las aristas se agregan para formar cada árbol. 5. a b c e g d f 1 8 10 9 7 3 4 2 6 5 6. 10 76 5 4 3 2 12 13 10 2 4 7 8 15 5 18 20 19 Uso del algoritmo de Prim partiendo del vértice a o 0 encuentre un árbol expandido mínimo para cada una de los grafos en los ejercicios 7 y 8. Indique el orden en que se agregan las aristas para formar cada árbol. 7. El grafo del ejercicio 5. 8. El grafo del ejercicio 6. Para cada uno de los grafos en los ejercicios 9 y 10, encuentre todos los árboles de expansión mínimos que pueden obtenerse mediante a) el algoritmo de Kruskal y b) el algoritmo de Prim partiendo de un vértice a o t. Indique el orden en que se agregan las aristas para formar cada árbol. 9. 4 4 4 1 5 3 3 7 7 11 12 10 a g f b c d e 10. t w x y z u