Embed Size (px)
Citation preview
Electivo I
Unidad I
Grafos
Semana 4
Estructuras y Compresión de datos
Competencia General
Implementa algoritmos y estructuras de
datos avanzados, haciendo énfasis en los
algoritmos de internet, seguridad y redes.
Capacidades Específicas
• Comprende la naturaleza de los
algoritmos asociados a estructuras de
datos avanzados.
• Implementa algoritmos utilizando
estructura de datos avanzadas
Procedimientos
Implementar algoritmos fundamentales
para la solución de problemas basados
en la teoría de grafos.
Co
nte
nid
os
Algoritmos sobre grafos elementales
Conectividad
Grafos ponderados
Árbol de expansión mínimo
Camino mas corto
Glosario Grafo: Un grafo es una colección
de vértices y aristas.
– Los vértices son objetos simples que
pueden tener un nombre y otras
propiedades;
– Una arista es una conexión entre
dos vértices.
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
A
B C G
D E
F
A
B G
E
F
Camino: Un camino entre los
vértices x e y de un grafo es una
lista de vértices en la que dos
elementos sucesivos están
conectados por aristas del grafo.
Glosario Grafo conexo: Un grafo es conexo
si hay un camino desde cada
nodo hacia otro nodo del grafo.
Grafo no conexo: Esta constituido
por componentes conexos.
Camino simple: Es un camino en el
que no se repite ningún vértice.
Ciclo: es un camino simple con la
característica de que el primero y
el ultimo vértices son el mismo.
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
A
B C G
D E
F
A
B
G
D E
F
A
B G
E
F
A G
E
F
Glosario Grafo completo: Son los grafos con
todas las aristas posibles.
Grafo disperso: Tienen
relativamente pocas aristas.
Grafo denso: Les falta muy pocas
aristas de todas las posibles.
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
A
G
E F
A
G
E F
A
G
E F
Representación de un grafo
Matriz de adyacencia:
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
A
B C G
D E
F
A B C D E F G
A 1 1 1 0 0 1 1
B 1 1 0 0 0 0 0
C 1 0 1 0 0 0 0
D 0 0 0 1 1 1 0
E 0 0 0 1 1 1 1
F 1 0 0 1 1 1 0
G 1 0 0 0 1 0 1
Se construye un array de V*V
valores booleanos en el que a[x][y]
es igual a 1 si existe una arista
desde el vértice x al y, caso
contrario es igual a 0.
Es de destacar que en realidad cada arista se representa con dos bits:
una arista que enlace x e y se representa con valores verdaderos tanto
en a[x][y] como en a[y][x].
La matriz de
adyacencia
solo es
satisfactoria si
los grafos a
procesar son
densos.
Lista de adyacencia:
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
A
B C G
D E
F
La lista de adyacencia se adapta mejor a lo casos en los que
los grafos a procesar no son densos.
A B C D E F G
F A A A A
B
C
G
E
F
D
D F
G E
E
Representación de un grafo
Recorridos en un grafo
En una gran cantidad de problemas
con grafos, es necesario visitar
sistemáticamente los vértices y aristas
del grafo.
La búsqueda en PROFUNDIDAD y en
AMPLITUD, son dos técnicas importantes de recorrido del grafo.
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
Búsqueda en Profundidad (BEP)
• Se comienza en el vértice inicial (vértice con
índice 1) que se marca como vértice activo.
• Hasta que todos los vértices hayan sido visitados,
en cada paso se avanza al vecino con el menor
índice siempre que se pueda, pasando este a ser
el vértice activo.
• Cuando todos los vecinos al vértice activo hayan
sido visitados, se retrocede al vértice X desde el
que se alcanzó el vértice activo y se prosigue
siendo ahora X el vértice activo.
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
Búsqueda en Profundidad
a b
d e
c
a b
d e
c
a b
d e
c
a b
d e
c
a b
d e
c
a b
d e
c
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
La estructura utilizada para guardar los nodos a visitar en este
tipo de búsqueda es una pila o stack (de procedimiento
recursivo).
Búsqueda en Amplitud (BEA)
• Se comienza en el vértice inicial (vértice con índice
1) y se marca como vértice activo, a diferencia
con la BEP ahora se visitan en orden creciente de
índice todos los vecinos del vértice activo antes de
pasar al siguiente.
• Hasta que todos los vértices hayan sido visitados,
en cada paso se van visitando en orden creciente
de índice todos los vecinos del vértice activo.
• Cuando se han visitado todos los vecinos del
vértice activo, se toma como nuevo vértice activo
el primer vértice X visitado después del actual
vértice activo. Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
Búsqueda en Amplitud
a b
d e
c
0 a b
d e
c
0 1
1
1
a b
d e
c
0 1
1
1 2
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
En la búsqueda en
amplitud se utiliza una
cola para guardar tales
nodos a visitar.
Uso de los Recorridos
Ambos recorridos se pueden usar para resolver los
siguientes problemas:
– Probar que G es conectado.
– Obtener un árbol de expansión de G.
– Obtener los componentes conectados de G.
– Obtener un camino entre dos vértices dados de G, o
indicar que no existe tal camino.
El recorrido BEP se usa para:
– Obtener un ciclo en G, o indicar que G no tiene ciclos.
El recorrido BEA se usa para:
– Obtener para cada vértice V de G, el número mínimo de
aristas de cualquier camino entre S y V. Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
Laberintos
La búsqueda en profundidad fue expuesta
formalmente como un método para
recorrer laberintos.
Alg
oritm
os
sob
re g
rafo
s e
lem
en
tale
s
El grafo se construye colocando un
vértice en cada punto en el que existe
mas de un camino a tomar y a
continuación se conectan los vértices de
acuerdo con esos caminos.
• La búsqueda en profundidad es apropiada para la búsqueda de un
elemento en el laberinto por una sola persona, dado que el “siguiente
lugar a visitar” esta siempre próximo;
• La búsqueda en amplitud es mas apropiada para un grupo de
personas que buscan el mismo elemento desplazándose en todas las
direcciones a la vez
Problemática Se examinará una generalización de la conectividad denominada biconectividad, cuyo interés reside en conocer si hay mas de un medio de pasar de un vértice de un grafo a otro.
Co
ne
ctiv
ida
d
Grafo biconexo: Un grafo es
biconexo, si solo si, existen al menos
dos caminos diferentes que conecten
cada par de vértices. De esta forma
si se suprime un vértice y todas las
aristas que inciden en el, el grafo
permanece conexo.
A
G
E F
“Si para algunas aplicaciones es importante que un grafo sea
conexo, es también importante que permanezca conexo”
Problemática Una versión particular del problema de la conectividad, se da con frecuencia en lo que concierne a la situación dinámica en las que las aristas se añaden al grafo una a una, intercalando preguntas sobre si dos vértices determinados pertenecen o no a la misma componente conexa.
El problema se denomina a veces como “unión-pertenencia”.
Co
ne
ctiv
ida
d
Componentes conexas
• De un grafo no dirigido
– Se puede saber si es conexo, si no
lo, es se pueden conocer sus
componentes Conexas
• Conjunto W, de vértices del grafo
• En el cual hay camino desde
cualquier V1 a cualquier V2
• Donde V1 y V2 pertenecen a W
A
C
B
D
E A
C
B
D
E
CONEXO
No CONEXO
Componentes conexas: entre ellas son conexas
Co
ne
ctiv
ida
d
Biconectividad A veces es útil diseñar mas de una ruta entre puntos de un grafo, aunque solo sea para identificar posibles fallos en los puntos de conexión (vértices). Esto nos permitiría tener recorridos alternativos por ejemplo para llegar de una ciudad a otra.
Co
ne
ctiv
ida
d
A
G
E F
Puntos de articulación
En un grafo no dirigido conexo:
• Existen vértices que si se eliminan
– “Desconectan” al Grafo y lo dividen en componentes conexas
• Estos vértices “clave” son puntos de articulación
• Si un grafo no tiene Punto de Articulación
– Es biconexo
• La conectividad de un grafo
– Es el numero de nodos que se necesitan eliminar para dejar a
un grafo “desconectado”
Un punto de articulación en un grafo conexo es un
vértice que si se suprime romperá el grafo en dos o
mas piezas.
Co
ne
ctiv
ida
d
Ejemplo
A
D
C
B
E
F
Puntos de Articulación
Puntos de articulación C
on
ec
tiv
ida
d
Árbol de expansión
Definición: Un árbol T es un árbol de expansión de un grafo G si T es un
subgrafo que contiene a todos los vértices de G.
Co
ne
ctiv
ida
d
Árbol de expansión
• Para poder calcular los Puntos de Articulación de un grafo
– Hay que obtener el árbol de expansión
• Este se obtiene
– A partir del Recorrido en Profundidad
Ejemplo:
A
D
C
B
E
F
A
C
F
E
B
D
Arco en Retroceso: Cuando se quiere visitar un nodo que ya ha sido visitado y no es el padre
Co
ne
ctiv
ida
d
Como representar el árbol de
expansión • Un árbol en expansión
– No es un árbol binario
– Cada Vértice puede tener 0, 1 o n hijos
• Si no tomamos en cuenta los arcos en
retroceso, la representación depende del Grafo
– Matriz de Adyacencia -> Usar un arreglo
– Lista de Adyacencia -> Una lista
• La representación mostrará quien es el padre de
cada nodo
Co
ne
ctiv
ida
d
Árbol de expansión con Matriz
de Adyacencia
• Los vértices del grafo
– Se encuentran en un arreglo
– Cada índice del arreglo
• Representa un vértice
• Ej: A – 0, B – 1, etc.
• Al representar el árbol de expansión
– El padre(índice) de cada nodo
puede almacenarse en un arreglo
• Que también represente a los vértices
A
D
C
B
E
F
0 4 0 0 5 2 0
A
1
B
2
C
3
D
4
E
5
F
Co
ne
ctiv
ida
d
0 1
2
3
4
5
Árbol de expansión con Lista de
Adyacencia
• Los vértices del grafo
– Se encuentran en una lista
– Cada nodo representa un vértice
• Al representar el árbol de expansión
– De cada nodo de esta lista solo nos interesa
conocer al padre
– Se puede añadir un dato al nodo vértice
• Un enlace con el padre
A
D
C
B
E
F
A
B
C
D
E
F
Co
ne
ctiv
ida
d
Unión - Pertenencia C
on
ec
tiv
ida
d
En algunas aplicaciones se desea simplemente conocer si un vértice x esta o no conectado a un vértice y de un grafo, sin que sea importante el camino que los conecta.
Los grafos se corresponden de forma natural con los conjuntos (colecciones de objetos): los vértices representan a los objetos y las aristas significan “esta en el mismo conjunto que”.
A B
C
G
D E
F
{A F D E}
{B C G} Conjuntos
ó clases de
equivalencia
Cada componente conexa
corresponde a una clase de
equivalencia diferente
Unión - Pertenencia C
on
ec
tiv
ida
d
El añadir una arista se corresponde con la combinación de las clases de equivalencia representadas por los vértices a conectar.
El interés se centra en la pregunta fundamental “x es equivalente a y” ó “¿está x en el mismo conjunto que y?”. Esto se corresponde claramente con la pregunta fundamental de los grafos “¿está el vértice x conectado al vértice y?”
“Dado un conjunto de aristas, se puede construir una
representación por lista de adyacencia que corresponda al
grafo y utilizar la búsqueda en profundidad para asignar a
cada vértice el índice de su correspondiente conexa y
responder a las preguntas antes planteada con tal solo dos
accesos a arrays y una comparación”
Unión - Pertenencia C
on
ec
tiv
ida
d
Por correspondencia con el problema de los conjuntos, la adición de una nueva arista se denomina una operación de unión, y las preguntas se denominan operaciones de pertenencia.
El objetivo es escribir una función que pueda verificar si dos vértices x e y pertenecen al mismo conjunto (o,
en representación de grafos, a la misma componente conexa) y, en caso de que sea así, que pueda unirlos en el mismo
conjunto (colocando una arista entre ellos y el grafo).
En lugar de construir una lista de adyacencia directa o cualquier otra representación de los grafos, es mas eficaz utilizar una estructura interna orientada específicamente a la realización de las operaciones unión y pertenencia.
Unión - Pertenencia C
on
ec
tiv
ida
d
En resumen:
• Esta estructura interna es un bosque de arboles, uno por cada componente conexa.
• Se necesita poder encontrar si dos vértices pertenecen al mismo árbol y combinar dos arboles en uno.
Problemática Con frecuencia se desea modelar problemas prácticos utilizando grafos en los que se asocia a las aristas unos pesos o costes.
En un mapa de líneas aéreas, en el que las aristas representan rutas de vuelo, los pesos pueden representar distancias o tarifas. Estas situaciones hacen aparecer de forma natural cuestiones como el minimizar costes.
Gra
fos
po
nd
era
do
s
Problemática Se examinara los algoritmos de dos de estos problemas:
1. Encontrar la forma de conectar todos los puntos al menor coste (problema del árbol de expansión mínima).
2. Encontrar el camino de menor coste entre dos puntos dados (problema del camino mas corto).
G
rafo
s p
on
de
rad
os
La forma de representar a los grafos ponderados es obvia.
• En la representación por matriz de adyacencia, la matriz puede
contener pesos de aristas en lugar de valores booleanos y
• En la representación por listas de adyacencia se puede añadir un
campo a cada elemento de la lista, a manera de peso.
Árbol de Expansión Mínimo
(AEM) Un árbol de expansión mínimo de un grafo ponderado es una colección de aristas que conectan todos los vértices y en el que la suma de los pesos de las aristas es al menos inferior a la suma de los pesos de cualquier otra colección de aristas que conecten todos los vértices.
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo genérico
• Se puede construir el árbol de expansión mínimo comenzando en cualquier vértice y tomando siempre el vértice mas próximo de todos los que se hayan elegido.
• En otras palabras; se busca la arista de menor peso entre todas las que conectan vértices que ya están en el árbol, con vértices que no lo están todavía, y después se añade al árbol la arista y el vértice a los que conduce la anterior. G
rafo
s p
on
de
rad
os
- A
EM
Algoritmo de Kruskal – paso
a paso Tengamos el siguiente grafo no dirigido.
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso En primer lugar usaremos el método MakeSet de unión-find para inicializar cada componente, obteniendo las siguientes componentes conexas iniciales:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Ahora el siguiente paso es ordenar las aristas del grafo en orden ascendente:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Lo siguiente será recorrer todas las aristas ya ordenadas y verificar si sus vértices están o no en la misma componente.
La primera arista a verificar es la que une a los vértices 8 y 7, verificamos si están en la misma componente, para ello hacemos Find(8) , Find(7):
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Como podemos observar en la tabla y en la misma imagen no están en la misma componente conexa, por tanto esta arista es valida para el árbol de expansión mínima (AEM) así que unimos los vértices por el método de Union( 8 , 7 ).
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Continuamos con la siguiente arista:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Observamos la tabla de Union-Find y vemos que Find(3) != Find(9). Entonces es posible realizar la unión de ambas componentes:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Continuamos con la siguiente arista:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso En la imagen podemos observar que ambos vértices no están en la misma componente, por tanto realizamos la Union( 6 , 7 ):
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Continuamos con la siguiente arista, los vértices 1 y 2 no están en la misma componente conexa:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Realizamos la Union(1,2):
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Continuamos con la siguiente arista:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Al observar la imagen los vértices 3 y 6 están en distinta componentes conexas. Entonces realizamos la Union(3,6) y actualizamos la tabla de Union-Find.
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Continuamos con la siguiente arista:
En este caso si
observamos la imagen los
vértices 7 y 9 están en la
misma componente
conexa; asimismo en la
tabla de Union-Find el
elemento raíz del vértice
7 es el mismo que el del
vértice 9 por ello
afirmamos que están el a
misma componente
conexa, por lo tanto no
habrá que realizar la
unión de ambos vértices.
Con esto evitamos tener
ciclos en el árbol de
expansión mínima.
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Continuamos con la siguiente arista:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Al observar la imagen los vértices 3 y 4 no están en la misma componente conexa por lo tanto realizamos la Union(3,4) en el grafo:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Continuamos con la siguiente arista:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Los vértices 8 y 9 están en la misma componente conexa por lo tanto no realizamos Unión de vértices. Continuemos con la siguiente arista:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Los vértices 1 y 8 están diferentes componentes. Realizamos la Union(1,8) en el grafo:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Continuamos con la siguiente arista:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Los vértices 2 y 3 están en la misma componente conexa por lo tanto no realizamos Union de componentes. Continuamos con la siguiente arista:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Los vértices 4 y 7 no están en la misma componente conexa, realizamos Union(4,5) en el grafo:
Gra
fos
po
nd
era
do
s -
AEM
Algoritmo de Kruskal – paso
a paso Como podemos observar ya están todos los vértices del grafo conectados así que al momento de continuar viendo las demás aristas ordenadas siempre tendremos e l caso de que ya están en la misma componente conexa por lo tanto el Árbol de Expansión Mínima para el grafo es el siguiente:
El peso total del árbol de expansión mínima para el grafo mostrado
es 39.
Gra
fos
po
nd
era
do
s -
AEM
Verificación del Arbol de
Expansión Mínima (AEM) Para que sea un AEM válido, el número de aristas debe ser igual al número de vértices – 1. Esto se cumple debido a que el AEM debe poseer todos los vértices del grafo ingresado y además no deben existir ciclos. Si vemos el ejemplo antes explicado tenemos en el AEM:
Número de Aristas = 8
Número de Vértices = 9
Cumple con lo dicho -> 9 – 1 = 8
por tanto tenemos un AEM válido
Gra
fos
po
nd
era
do
s -
AEM
Camino mas corto (CMC)
• El problema del camino mas corto consiste en encontrar entre todos los caminos que conectan a dos vértices x e y dados de un grafo ponderado el que cumple con la propiedad de que la suma de las ponderaciones de todas las aristas sea mínima.
• Si las ponderaciones son todas iguales a 1, entonces el problema sigue siendo interesante: ahora consiste en encontrar el camino que contenga al mínimo de aristas que conecten a x e y.
Gra
fos
po
nd
era
do
s -
CM
C
Algoritmo de Dijkstra
El algoritmo de Dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos.
Gra
fos
po
nd
era
do
s -
CM
C
Algoritmo de Dijkstra
Como trabaja:
Gra
fos
po
nd
era
do
s -
CM
C
Primero marcamos todos los vértices como no utilizados. El algoritmo parte de un vértice origen que será ingresado, a partir de ese vértices evaluaremos sus adyacentes, como dijkstra usa una técnica greedy -La técnica greedy utiliza el principio de que para que un camino sea óptimo, todos los caminos que contiene también deben ser óptimos- entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación.
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Tengamos el siguiente grafo, cuyos ID están en color negro encima de
cada vértice, los pesos están en color azul y la distancia inicial en cada
vértice es infinito.
Hallaremos la distancia mínima partiendo del vértice 1 hacia los otros
vértices.
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Inicializamos los valores de nuestros arreglos.
Donde: • Vértices: ID de los vértices. • Distancia[ u ]: Distancia mas corta desde vértice inicial a vértice con ID = u. • Visitado[ u ]: 0 si el vértice con ID = u no fue visitado y 1 si ya fue visitado. • Previo[ u ]: Almacenara el ID del vértice anterior al vértice con ID = u, servirá
para impresión del camino mas corto.
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
De acuerdo al vértice inicial que elijamos cambiara la distancia inicial,
por ejemplo la ruta más corta partiendo del vértice 1 a todos los demás
vértices:
El vértice 1 es visitado, la distancia de vértice 1 al vértice 1 es 0
por estar en el mismo lugar.
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Hasta este momento la tabla quedaría de la siguiente manera.
Ahora vemos sus
adyacentes que no
hayan sido visitados.
Tendríamos 2 y 4.
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Evaluamos primero para el vértice 2
Vemos que la distancia actual desde el vértice inicial a 2 es ∞,
verifiquemos el paso de relajación:
(distancia[ 1 ] + 7) < distancia[ 2 ] -> 0 + 7 < ∞ -> 7 < ∞
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
El paso de relajación es posible realizarlo entonces actualizamos la
distancia en el vértice 2 y agregando el vértice en la cola de prioridad
con nueva distancia quedando:
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Ahora evaluamos al siguiente adyacente que es el vértice 4:
De manera similar al anterior vemos que la distancia actual desde el
vértice inicial a 4 es ∞, verifiquemos el paso de relajación:
(distancia[ 1 ] + 2) < distancia[ 4 ] -> 0 + 2 < ∞ -> 2 < ∞
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
El paso de relajación es posible realizarlo entonces actualizamos la
distancia en el vértice 4 quedando:
En cuanto a la cola de prioridad como tenemos un vértice con
menor peso, este nuevo vértice ira en el tope de la cola:
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Revisamos sus adyacentes no visitados que serian los vértices 2, 3 y 5.
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Evaluamos primero para el vértice 2
Ahora vemos que la distancia actual del vértice inicial al vértice 2 es
7, verifiquemos el paso de relajación:
(distancia[ 4 ] + 3) < distancia[ 2 ] -> 2 + 3 < 7 -> 5 < 7
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
En esta oportunidad hemos encontrado una ruta mas corta partiendo
desde el vértice inicial al vértice 2, actualizamos la distancia en el
vértice 2 y actualizamos el vértice previo al actual quedando:
En cuanto a la cola de
prioridad como tenemos un
vértice con menor peso este
nuevo vértice ira en el tope de
la cola, podemos ver que
tenemos 2 veces el mismo
vértice pero como usamos una
técnica greedy siempre
usaremos el valor óptimo:
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Continuamos con los Vértices 3 y 5, como tienen valor si será posible
relajarlos, por lo que sería similar a los pasos iniciales solo que en los
pasos iniciales distancia[ 1 ] era 0 en este caso distancia[ 4 ] es 2,
quedando:
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Hemos terminado de evaluar al vértice 4, continuamos con el tope de
la cola que es vértice 2, el cual marcamos como visitado.
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Los adyacentes no visitados del vértice 2 es el vértice 3.
Ahora vemos que la distancia actual del vértice inicial al vértice 3 es
10, verifiquemos el paso de relajación:
(distancia[ 2 ] + 1) < distancia[ 3 ] -> 5 + 1 < 10 -> 6 < 10
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
En esta oportunidad hemos encontrado una ruta mas corta partiendo
desde el vértice inicial al vértice 3, dicha ruta sería 1 -> 4 -> 2 -> 3 cuyo
peso es 6 que es mucho menor que la ruta 1 – > 4 -> 3 cuyo peso es 10,
actualizamos la distancia en el vértice 3 quedando:
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
El siguiente vértice de la cola de prioridad es el vértice 3 y su único
adyacente no visitado es el vértice 5.
Vemos que la distancia actual del vértice inicial al vértice 5 es 7,
verifiquemos el paso de relajación:
(distancia[ 3 ] + 5) < distancia[ 5 ] -> 6 + 5 < 7 -> 11 < 7
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
En esta oportunidad no se cumple por lo que no relajamos el vértice 5.
La tabla en cuanto a distancias no sufre modificaciones y no
agregamos vértices a la cola:
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Ahora tocaría el vértice 2 pero como ya fue visitado seguimos
extrayendo elementos de la cola, el siguiente vértice será el 5.
Algoritmo de Dijkstra – paso
a paso
Gra
fos
po
nd
era
do
s -
CM
C
Al ser el ultimo vértice a evaluar no posee adyacentes sin visitar por lo
tanto hemos terminado el algoritmo. En el grafico anterior observamos
que 2 aristas no fueron usadas para la relajación, las demás si fueron
usadas. La tabla final quedaría de la siguiente manera:
De la tabla si deseo saber la distancia mas corta del
vértice 1 al vértice 5, solo tengo que acceder al valor
del arreglo en su índice respectivo (distancia[ 5 ]).
Algoritmo de Dijkstra – Impresión camino encontrado
Gra
fos
po
nd
era
do
s -
CM
C
En el proceso anterior usábamos el arreglo previo[ u ] para almacenar
el ID del vértice previo al vértice con ID = u, ello me sirve para formar el
árbol de la ruta mas corta y además me sirve para imprimir caminos de
la ruta mas corta.
Algoritmo de Dijkstra – Impresión camino encontrado
Gra
fos
po
nd
era
do
s -
CM
C
Para imprimir el camino mas corto deseado usamos el arreglo previo[ u ],
donde u tendrá el ID del vértice destino, o sea si quiero imprimir el
camino mas corto desde vértice 1 -> vértice 3 partiré desde previo[ 3 ]
hasta el previo[ 1 ].
Veamos gráficamente el funcionamiento, desde el grafo comenzamos
en 3
Algoritmo de Dijkstra – Impresión camino encontrado
Gra
fos
po
nd
era
do
s -
CM
C
El previo de 3 es el vértice 2, por lo tanto ahora evaluó 2:
Algoritmo de Dijkstra – Impresión camino encontrado
Gra
fos
po
nd
era
do
s -
CM
C
Ahora el previo de 2 es el vértice 4:
Algoritmo de Dijkstra – Impresión camino encontrado
Gra
fos
po
nd
era
do
s -
CM
C
El previo de 4 es el vértice inicial 1
Como el previo de 1 es -1 terminamos el recorrido, ahora en el
retorno de las llamadas recursivas imprimo el camino: 1 4 2 3
Electivo I
Unidad I
Grafos
Semana 4
Estructuras y Compresión de datos
