REPÚBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER POPULAR PARA EDUCACIÓN UNIVERSITARIA

UNIVERSIDAD POLITÉCNICA TERRITORIAL DE LOS VALLES DEL TUY
SEDE: TOMAS LANDER
PNF: INGENIERÍA EN MANTENIMIENTO
TRAYECTO 4– SEMESTRE 2

LOS GRAFOS

Facilitador:
Participante:
Prof. Alexis Alfredo Javier Tesorero Velásquez
1.- INTRODUCCIÓN
Un grafo es una estructura de datos utilizada para representar una
colección de elementos, caracterizada porque cada objeto puede tener cero,
uno o muchos objetos anteriores o siguientes. Es un concepto matemático
con aplicaciones en muchos campos como son la informática, el transporte,
la ingeniería eléctrica, etc...

Como tipo abstracto de dato, un grafo es un par compuesto por dos

conjuntos, V y A. Al conjunto V se le llama conjunto de vértices o nodos
del grafo. Un vértice es un objeto simple que puede tener un nombre y otras
propiedades. A es un conjunto de pares de vértices a los que se conoce con
el nombre de arcos o aristas. Un arco es, por tanto, una conexión entre dos
pares de vértices.

Para identificar un grafo se suele utilizar la notación G = (V,A).

Hay que tener en cuenta que la definición de grafo es independiente de
la representación.

La definición de grafo como tipo de dato abstracto viene dada por :

Grafo = registro de
N: numérico; {numero de vértices}
A: numérico; {numero de aristas}
M: vector [1..MAX,1..MAX] de numérico;
V: vector [1..MAX] de cadena;
Fin registro;

Los grafos se pueden clasificar en dos grupos principales:

 Dirigidos: son aquellos cuyas aristas son de sentido único.

Generalmente, se representan los nodos por círculos y los arcos por
flechas que indican el sentido en el que van.
  No dirigidos: en ellos no se distingue la dirección en la que va la
arista. Los nodos se representan por círculos y las aristas por
segmentos. En estos grafos, la arista (v1, v2) es la misma que la
(v2,v1). Si la agregáramos, A tendría elementos repetidos y esto no
es posible por ser A conjunto.

Si se asocia a cada arista un peso o valor, un valor entero, diremos

que se trata de un grafo ponderado. Estos pesos representan, por
ejemplo, distancias o costes. Los grafos dirigidos y ponderados se
denominan redes.

1.1 DEFINICIONES BÁSICAS

 SUCESOR O ADYACENTE: se dice que y es sucesor del nodo x
si existe un nodo que tenga por origen x y por destino y, es decir, que
el arco (x, y) pertenezca a A.

 PREDECESOR: Se dice que el nodo y es predecesor del nodo x si

existe un arco que tenga por origen a y y por destino a x, es decir si
el arco (y, x) pertenece a A. Al conjunto de nodos predecesores de x
lo denotaremos con P(x). Ej: P(v4) = { v1, v2, v5 }, P(v2) ={ v1, v2}
  CAMINO: Dado un grafo G=(V,A), decimos que existe un camino
de x a y si existe una secuencia <v0,...,vn-1> tal que:

a) v0= x y vn-1= y
b) (vi-1, vi) pertenece a A con i=1..n-1

 GRAFO FUERTEMENTE CONECTADO: aquél en el que existe

un camino entre cualquier par de nodos del grafo.

 GRAFOS COMPLETOS: aquéllos en los cuales para cualquier par

de nodos u, v de V (con u distinto de v) existe una arista (u, v) de A.
Tienen exactamente n(n-1)/2 aristas si es no dirigido y n(n-1) si es
dirigido, donde n es el número de vértices del grafo.

 GRAFOS DISPERSOS: son los que tienen relativamente pocas

aristas (menos de VlogV, donde V es el número de vértices).

 GRAFOS DENSOS: grafos a los que les falta muy pocas aristas de
todas las posibles para llegar a ser completos.

1.2 OPERACIONES DEL TDA GRAFO.

Hay varias operaciones respecto a los grafos ( añadir_vértice(),

borrar_vértice(), añadir_arista(), borrar_arista(), etc). Nos centraremos
en algunas de ellas, haciendo seguidamente un breve resumen de lo
principal de cada una:

Algoritmo crear_grafo (G: Grafo, ok: lógico)es

{nec.: un grafo y un valor lógico.
mod.:ok indicando si la operación tuvo éxito o no, será cierto si el grafo
se creo correctamente, falso en caso contrario.
prod.:una estructura de grafo.}

Algoritmo borrar_grafo(G: grafo)es

{nec.: un grafo.
mod.:borra el grafo}

Algoritmo posición (V, X, N, P, EXISTE) es

{nec: el vector de nombres del grafo, el número de posiciones ocupadas
en el vector, un numérico y un lógico que nos dirá si ha habido errores
prod: un numérico que nos da la posición en la que se encuentra el nodo
que dábamos}
 Algoritmo conexiones(n: cadena, G: grafo)es
{nec.: un grafo y un nodo del grafo.
prod.: muestra por pantalla los nodos adyacentes a uno dado.}

Algoritmo recorrido_anchura(G: Grafo)es

{nec.:un grafo
prod.: muestra por pantalla el orden en que se visitaron los nodos en el
recorrido}

Algoritmo recorrido_profundidad (G: Grafo) es

{nec: un grafo
prod: muestra por pantalla un vector en el que indica el orden en que se
visitaron los nodos al recorrer el grafo}

Algoritmo Dijkstra (G: Grafo, v1, v2: cadena) es

{nec: un grafo y dos vértices
prod: da el valor del costo del camino mínimo entre los dos nodos
dados}

Algoritmo Floyd (G:Grafo) es

{nec: un grafo
Prod: una matriz en la que muestra el costo del camino mínimo entre
dos nodos del grafo y una matriz que indica si pasa por algún nodo
alternativo}

2.- OPERACIONES BÁSICAS

Nos dirigimos con este nombre a las operaciones de crear grafo,
borrar grafo, posición y conexiones.

 CREAR GRAFO
 Implementamos seguidamente el algoritmo que se encarga de esta
operación:

Algoritmo crear_grafo (G, ok) es

G: Grafo; {p.dato-resultado}
Ok: lógico; {p. Resultado; será cierto si el grafo se creo correctamente, falso en caso
contrario}
n1, n2: cadena;
peso, x, y: numérico;
existe: lógico;

Inicio

Escribir “numero de vértices:”;

Leer G.N;
Escribir “numero de aristas:”;
Leer G.A;
Si G.N > MAX o G.A > MAX2 entonces

ok:= falso;

sino     ok:= cierto;

fin si ;

{pedimos el nombre de los nodos y los vamos guardando en G.V }

para i desde 1 hasta G.N hacer

escribir “primer vértice del arco”, i, “-ésimo”;

leer n1;

posición(G.V, n1, G.V, x, existe);

escribir “segundo vértice del arco”, i, “-ésimo”;

leer n2;

posición(G.V, n2, G.V, y, existe1);

si existe= falso o existe1= falso entonces

ok:= falso;

si no

escribir “peso del arco asociado”;

leer peso;
 G.M(x,y):= peso;

ok:=cierto;

fin si;

fin para;

fin;

 BORRAR GRAFO

Su función es eliminar un grafo que teníamos. La implementación

en algorítmico de este grafo es :

Algoritmo borrar_grafo(G) es

G: Grafo; {p.dato-resultado}

Inicio
G.V:=0;
G.A:=0;
Fin;

 POSICIÓN
Algoritmo posición(V, X, N, P, Existe) es

V: vector [1..MAX] de cadena; {p,dato}

X: cadena; {p, dato; elemento que estamos buscando}
N: numérico; {p. dato; numero de posiciones ocupadas del vector}
P: numérico; {p. resultado; posición del elemento, si está }
Existe: lógico; {p. resultado; indicará si hemos encontrado el elemento }

Inicio
P:=1;
Existe:=falso;
Mientras P <=N y Existe= falso hacer

Si V(P)=X entonces

Existe:=cierto;

Sino

P:=P+1;
 Fin si ;

Fin mientras;

Fin ;

 CONEXIONES

La implementación de este algoritmo es:

Algoritmo conexiones(n, G) es

n: cadena;{p. dato; el nombre del nodo del que queremos ver los nodos adyacentes}
G: Grafo; {p. dato}
x, j: numérico;
con: vector[1..MAX]; {contiene los nodos adyacentes al nodo dado}

Inicio
posición(G.V, n, G.N, x, existe);
si  not existe entonces

escribir “ERROR el nodo dado no existe”;

si no

{contamos el numero de nodos adyacentes}

j:=0;

para i desde 1 hasta G.N hacer

si G.M (x,i)<>0 hacer

j:=j+1;

fin si ;

fin para;

{inicializamos con a cero}

para i desde 1 hasta j hacer

con(i):=0;
 fin para ;

i:=1;

k:=1;

mientras i<=G.V AND k<=j hacer

si G.M(x,i)<>0 AND con(k)=0 entonces

con(k):=i;

fin si;

k:=k+1;

i:=i+1;

fin mientras;

escribir “los nodos adyacentes a”, n, “son”;

para i desde 1 hasta j hacer

escribir G.V_NOM(con(i));

fin para ;

fin si;
fin;

3.- REPRESENTACIÓN DE GRAFOS

Existen varias maneras de representar un grafo pero dos son las
principales: matrices de adyacencia y listas de adyacencia. La selección
apropiada depende de las operaciones que se aplicarán a los vértices y a los
arcos del grafo, así como del tipo de grafo que estemos manejando.
 MATRICES DE ADYACENCIA.
Es un array bidimensional de dimensión nxn donde cada posición
(i,j) vale 0 si no hay ninguna arista del vértice i al j o vale el peso
asociado a la arista correspondiente en el caso de que sea ponderado.
Cabe destacar que si el grafo es no dirigido la matriz es simétrica.

La definición de tipo, si además en cada nodo hay un elemento, será:

tipo grafo = registro
vértices: tabla[1..n] de carácter;
adyacente: matriz[1..n, 1..n] de numérico;
fin registro;

A continuación mostramos un ejemplo de un grafo representado

mediante una matriz de adyacencia. Los espacios en blanco significan
que no existe una arista que una los vértices a los que se refiere.

Una de las principales ventajas de esta representación es que es

inmediato ver si dos nodos están conectados. Sin embargo, en
contraposición, para conocer cuántos arcos hay en el grafo debemos
mirar todas las posiciones del grafo, lo que supone un costo de n 2-n.
Además, si el número de nodos es muy grande y hay poca conectividad
 (pocas aristas en relación a las máximas posibles) se desperdicia
memoria.

 LISTAS DE ADYACENCIA
En este tipo de representación, las n filas de la matriz de adyacencia
se representan mediante n listas enlazadas. Hay, por tanto, una lista para
cada vértice
.
En las listas de adyacencia, lo que haremos será guardar por cada
nodo, además de la información que pueda contener el propio nodo,
una lista dinámica con los nodos a los que se puede acceder desde él. La
información de los nodos se puede guardar en un vector o en otra lista
dinámica.

La definición de es:
tipo lista = nodo
tipo nodo = registro:
Vértice = información;
Siguiente = lista;
fin registro;
tipo cabecera = tabla [1..n] de lista;

En el caso en que el grafo sea ponderado, es decir, los arcos tengan

pesos, se añade un campo valor al registro.

A continuación se presenta un ejemplo de un grafo representado

mediante una lista de adyacencia:
 Como ventaja de este método tenemos que, en general, se guarda
menor cantidad de elementos, sólo se reservará memoria para aquellos
arcos que existan. En contrapartida, estamos guardando más espacio
para cada uno de los arcos, pues añadimos el índice destino del arco y el
puntero al siguiente elemento de la lista de arcos.

En cuanto a las tareas relacionadas con el recorrido de los grafos

cabe destacar que supondrán sólo trabajar con los vértices existentes en
el grafo.

 COMPARACIÓN ENTRE MATRICES Y LISTAS DE

ADYACENCIA

Cada representación presenta unas ventajas e inconvenientes en

función de la operación que se quiera llevar a cabo o del tipo de grafo.
Destacamos en este apartado algunas de los aspectos más a tener en
cuenta:

 En función de la densidad del grafo: Si los grafos son densos, el

método mas apropiado es el de la matriz de adyacencia. En cambio,
si trabajamos con un grafo poco denso es más recomendable hacer
uso de las listas de adyacencia, ya que se estará reservando sólo la
memoria que se necesita.
 En cuanto al recorrido del grafo: con listas de adyacencia, el
recorrido del grafo supondrá sólo trabajar con los vértices existentes
en el grafo. Sin embargo, el recorrer un grafo representado por una
matriz de adyacencias implica tener que recorrer una a una todas las
posiciones de la matriz.

 Comprobar las relaciones entre nodos: mediante la matriz es muy

fácil determinar, a partir de dos nodos, si están o no relacionados.
Sólo es necesario acceder al elemento adecuado de la matriz y
comprobar el valor que guarda (si es 0 es que no están relacionados,
si es cualquier número distinto de 0 entonces hay una arista que los
une). En cambio, trabajando con listas de adyacencia supone
recorrer la lista de elementos adyacentes perteneciente al nodo
analizado.

 Encontrar sucesores: ésta será una operación más sencilla si

trabajamos con listas de adyacencia pues para cada nodo se añade el
puntero al siguiente elemento. En cuanto a la matriz, supone recorrer
toda ella, con lo que el orden de la operación será cuadrático (n^2).
4.- RECORRIDO DE GRAFOS
Recorrer un grafo supone intentar alcanzar todos los nodos que estén
relacionados con uno dado que tomaremos como nodo de salida.

Existen básicamente dos técnicas para recorrer un grafo. La diferencia

fundamental es el orden en que se visitan los diferentes vértices.

 RECORRIDO EN ANCHURA
Supone recorrer el grafo, a partir de uno dado, en niveles, es decir,
primero los que están a una distancia de un arco del nodo de salida,
después los que están a dos arcos de distancia y así sucesivamente hasta
alcanzar todos los arcos a los que se pueda llegar desde el nodo de
salida.

La diferencia a la hora de implementar el algoritmo según la

representación que se haya elegido para definir el grafo residirá en la
manera de los diferentes nodos adyacentes a uno dado. En el caso de
matrices de adyacencia, se tendrán que comprobar si los enlaces entre
los nodos existen en la matriz. En los casos de las listas de adyacencia
sólo habrá que recorrer las listas de enlaces que parten del nodo en
cuestión para averiguar qué nodos son adyacentes al estudiado.

La implementación de un programa que lleve a cabo esta operación

se puede hacer mediante una cola.

Exponemos seguidamente un ejemplo de un grafo recorrido en

anchura en el que tomamos el vértice 1 como vértice de partida:
- El vértice 1 se inserta en la cola y en el conjunto de visitado
vértice 1 se inserta en la cola (porExplorar : <1>) y en el
conjunto de visitados (visitados = {1})

- Sacar de la cola el vértice 1. Obtener todos sus adyacentes, en

este caso los vértices {2, 4}. Como no pertenecen al conjunto
de visitados se insertan en ese conjunto (visitados = {1, 2, 4})
y en la cola (porExplorar: <2, 4>)

- Sacamos de la cola el vértice 2. Obtenemos todos sus

adyacentes, en este caso los vértices {3, 4, 6}. Como 3 y 6 no
pertenecen al conjunto de visitados se insertan en ese conjunto
(visitados = {1, 2, 4, 3, 6}) y en la cola (porExplorar: <4, 3,
6>)

- Sacamos de la cola el vértice 4. Obtenemos todos sus

adyacentes, en este caso los vértices 3 y 7. Como el vértice 7
no pertenece al conjunto de visitados se inserta en dicho
conjunto (visitados = {1, 2, 4, 3, 6, 7}) y en la cola
(porExplorar: <3, 6, 7>)

- Sacamos de la cola el vértice 3. Obtenemos todos sus

adyacentes, en este caso el vértice {1}. Como ya pertenece al
conjunto de visitados no hacemos nada (porExplorar: <6, 7>)

- Sacamos de la cola el vértice 6. Obtenemos todos sus

adyacentes, en este caso el vértice {5}. Como no pertenece al
conjunto de visitados se inserta en ese conjunto (visitados =
{1, 2, 4, 3, 6, 7, 5}) y en la cola (porExplorar: <7, 5>)

- Sacamos de la cola el vértice 7. Obtenemos todos sus

adyacentes, en este caso el vértice {6}. Como ya pertenece al
conjunto de visitados no hacemos nada(porExplorar: <5>)

- Sacamos de la cola el vértice 5. Obtenemos todos sus

adyacentes, en este caso el vértice {7}. Como ya pertenece al
conjunto de visitados no se procesa

- La cola ya se vació terminando el recorrido en anchura y

produciendo el listado: 1 2 4 3 6 7 5
 Implementamos a continuación el algoritmo que se encarga de
recorrer el grafo en anchura:

Algoritmo recorrido_anchura(G) es
G: Grafo;
visitado: vector[1..MAX] de numérico; {visitado(i) vale 0 si el nodo no ha sido visitado,
1 en caso contrario}
cola: vector[1..MAX] de numérico; {cola(i)=p si el nodo i se ha visitado en p lugar}
primero, ultimo: numérico;
x, y: numérico;

Inicio
primero:=0;
ultimo:=1;
visitado(1):=1;
cola(1):=1;
mientras primero<> ultimo hacer

primero:= (primero+1) MOD G.N;

x:=cola[primero];

para i desde 1 hasta G.N hacer

si G.M(x,i)<>0 entonces

si visitado(i)=0 entonces

visitado(i):=1;

ultimo:=(ultimo+1)MOD G.N;

cola(ultimo):=i;

fin si ;

fin si ;

fin para ;

fin mientras ;
para i desde 1 hasta G.V hacer

escribir “el nodo visitado en”, i, “-esimo lugar es:”, G.V_NOM(cola(i));

fin para;
fin;
 RECORRIDO EN PROFUNDIDAD
El recorrido en profundidad trata de buscar los caminos que parten
desde el nodo de salida hasta que ya no es posible avanzar más. Cuando
ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en
busca de caminos alternativos, que no se estudiaron previamente.

La búsqueda en profundidad trabaja seleccionando un vértice v de V

como vértice de partida y se marca a v como visitado (se considera que
en un principio ningún nodo ha sido visitado). Después se recorre cada
vértice adyacente a v no visitado, marcando a cada uno como visitado y
usando recursivamente la búsqueda en profundidad. En el caso en que
algún vértice se quede sin visitar, se selecciona alguno de ellos como
nuevo vértice de partida y se repite este proceso hasta que todos los
vértices hayan sido visitados.

La implementación de este programa se puede realizar de forma

recursiva o mediante el uso de una pila.

Mostramos un ejemplo de recorrido en profundidad tomando 1 como

vértice de partida:

Estudiamos brevemente los pasos que se siguen en el recorrido en

profundidad de este grafo:
- Se marca como visitado el nodo 1 y se buscan los adyacentes,
que son 2 y 4.

- Elegimos el vértice 2, marcándolo como visitado y buscamos

sus adyacentes son el 3 y el 4.
 - Tomamos el camino del 3 y llegamos a 1 que ya ha sido
visitado, luego pasamos a otro vértice adyacente de 2: el 4.

- Marcamos como visitado al nodo 4 y se obtienen sus

adyacentes, que son el 3 y el 7. Como el 3 ya ha sido visitado
sólo tenemos que ir hacia el 7.

- Marcamos el 7 como visitado y obtenemos sus adyacentes, en

este caso el 6.

- Buscamos los adyacentes del 6 una vez que lo marcamos

como visitado y encontramos el 5.

- Tras éste, ya no nos queda ningún nodo por visitar, por lo que
el recorrido finaliza.

La implementación de dicho algoritmo es:

Algoritmo Recorrido_profundidad (G: Grafo) es

Val: vector [1..MAX] de numérico;

Id, i, k: numérico;

Inicio

Id:=0;

{iniciamos val a –1]

para k desde 1 hasta G.N hacer

val(k):= -1;
fin para;

para k desde 1 hasta G.N hacer

si val(k) = -1 entonces
visitar (k, val, G, id);
fin si;
fin para;

para i desde 1 hasta G.N hacer

Escribir “El nodo visitado en” i “-ésimo lugar es” G.V(val(i));
Fin para;

Fin;
Algoritmo visitar (k, val, G, id) es

K, id: numérico;
Val: vector [1..MAX] de numérico;
G: grafo;
T: numérico;

Inicio

Val(k):= id+1;
Para t desde 1 hasta G.N hacer
Si G.M(k, t)<> 0 y val(t) = -1 entonces
Visitar (t ,val, G, id);
Fin si;
Fin para;
Fin;
5.- BÚSQUEDA DE LOS CAMINOS
MÍNIMOS
Se trata de un problema muy común en el estudio de los grafos.
Distinguiremos la búsqueda del camino mas corto con un solo origen de
la búsqueda del camino más corto entre todos los pares.

 CAMINO MÍNIMO DESDE UN SOLO ORIGEN

El problema es determinar el costo del camino más corto desde el
origen, que será un vértice cualquiera elegido por el usuario, a todos los
demás vértices de V (recordamos que V es el conjunto de vértices del
grafo), donde la longitud de un camino es la suma de los costos de los
arcos del camino. Trabajaremos en este caso con grafos ponderados.

Para resolver este problema se manejará un algoritmo voraz,

caracterizados porque en cada iteración se selecciona la mejor opción
entre las disponibles. Este tipo de algoritmos se utiliza a menudo en
situaciones donde se traza de optimizar una función de coste sobre una
colección de objetos. La técnica usada en este caso es conocida como
Algoritmo de Dijkstra, que opera a partir de un conjunto S de vértices
cuya distancia más corta desde el origen ya es conocida. En principio, S
contiene sólo el vértice de origen. En cada paso, se agrega algún vértice
restante v a S, cuya distancia desde el origen es la más corta posible.
Suponiendo que todos los arcos tienen costo no negativo, siempre es
posible encontrar un camino más corto entre el origen y cualquiera de
los nodos restantes, v. En cada paso del algoritmo se utilizará un vector
D para registrar la longitud del camino mínimo entre el nodo
correspondiente y el origen. Una vez que S incluye todos los vértices, D
contendrá la distancia más corta del origen a cada vértice.

Puede hacérsele al algoritmo una pequeña modificación añadiéndole

un vector P tal que P[v] contenga el vértice inmediato anterior a v en el
camino más corto. Esto servirá para reconstruir el camino mínimo del
origen a v.

Como aplicación de este método, consideramos G un mapa de vuelos

en el cual cada vértice representa una ciudad y cada arista (u, v) una ruta
aérea de la ciudad u a la ciudad v. El peso de la arista que hemos
tomado representa el tiempo que se requiere para volar de u a v. La
solución del problema de los caminos con un solo origen para este
 grafo, en este caso dirigido, determinaría el tiempo de viaje mínimo para
ir de cierta ciudad a todas las demás del mapa.

La implementación de este algoritmo es la siguiente:

Algoritmo Dijkstra (G: grafo; v1, v2: cadena) es

i, j, k, u, w: numérico;
distan: vector [1..MAX] de numérico;
perm: vector [1..MAX] de numérico;
precede: vector [1..MAX] de numérico;
actual, dc, pd: numérico;
nueva, menor: numérico;

posición(G.V, v1,G. N, p1, Existe );

posición(G.V, v2,G. N, p2, Existe );

{inicializamos}

para i desde10 hasta G.N hacer

perm(i):= 0;
distan(i):= 1000;
fin para;

perm (w):)= 1;
distan (w):= 0;
actual := w;

mientras actual <> u hacer

menor := 1000;
dc:= distan (actual);
para i desde 1 hasta G.N hacer
si perm (i)= 0 entonces
nueva:= dc + G.M (actual, i);
si nueva < distan (i ) entonces
distan (i) := nueva;
precede (i) := actual;
fin si;
si distan (i) < menor entonces
menor := distan (i);
k:= i;
fin si;
fin si;
fin para;
actual := k;
perm (actual) := 1;
fin mientras;
 pd := distan (u);
Escribir “La distancia de” v1 “ a “v2” vale” pd;

Fin;

 CAMINO MÍNIMO ENTRE TODOS LOS PARES

Para la resolución de este problema se podría usar el algoritmo de
Dijkstra, tomando por turno cada vértice como vértice origen, pero una
forma más directa es mediante el llamado algoritmo de Floyd.
Partimos de un grafo representado a través de una matriz. Por
conveniencia, suponemos que los vértices están numerados.
El algoritmo de Floyd usa una matriz nxn (donde n en este caso sería
el número de vértices del grafo) en la que se calculan las longitudes de
los caminos más cortos. Inicialmente cada posición de dicha matriz
contiene el valor que hay en la matriz del grafo en la correspondiente
posición, haciendo valer infinito aquéllas en las que no haya arista que
una los dos vértices correspondientes. A continuación se hacen n
iteraciones en la matriz de la que partimos en el algoritmo y al final de
la k-ésima iteración la posición [i, j] de la matriz tendrá por valor la
longitud más pequeña de cualquier camino que vaya desde el vértice i
hasta el vértice j y que no pase por un vértice con un número mayor que
k. Es decir, i y j, los vértices extremos del camino, pueden ser cualquier
vértice, pero todo vértice intermedio debe ser menor o igual que k.
Si llamamos A a la matriz que estamos considerando en este
algoritmo, obtenemos Ak [i, j] (donde k es el subíndice que denota la k-
ésima iteración) comparando Ak-1[i, j], el costo de ir de i a j sin pasar por
k o cualquier otro vértice con numeración mayor, con A k-1[i, k]Ak-1[k,
j], el costo de ir primero de i a k y después de k a j, sin pasar a través de
un vértice con número mayor que k. Si el paso por el vértice k produce
un camino de costo menor que Ak-1[i, j], se elige ese costo para Ak[i, j].

A continuación se expone el algoritmo que lleva a cabo esta

operación:

Algoritmo Floyd (G: grafo) es

  i, j, k: numérico;

v1, v2: cadena;

Inicio
 Para i desde 1 hasta G.N hacer

Para j desde 1 hasta G.N hacer

C(i, j):= G.M(i, j);

P(i, j):= 0;

fin para;

fin para;

Para i desde 1 hasta G.N hacer

Para j desde 1 hasta G.N hacer

C(i, j):= 1000; {tomamos un número grande}

fin para;

fin para

para k desde 1 hasta G.N hacer

para i desde 1 hasta G.N hacer

para j desde 1 hasta G.N hacer

si C(i, k)+C(k, j) < C(i, j) entonces

C(i, j) := C(i, k) + C(k, j);

P(i, j):= k;

fin si;

fin para;

fin para;

fin para;

Escribir “Ésta es la matriz que muestra los costes de los caminos mínimos”;
  Para i desde 1 hasta G.N hacer

Para j desde 1 hasta G.N hacer

Escribir C(i, j);

fin para;

fin para;

Escribir “Ésta es la matriz que nos muestra si pasa por algún nodo alternativo para ir
del nodo i al j por el camino más corto”;

  Para i desde 1 hasta G.N hacer

Para j desde 1 hasta G.N hacer

Escribir P(i, j);

fin para;

fin para;

 Fin;

6.- BIBLIOGRAFÍA.
Libros:

- Algoritmos en C++, Addison – Wesley

Díaz de Santos
Autor: Robert Sedgemick

- Data Structures using

Autores: Aarón M. Tenenbaum, Yedidyah Langsam, Mosha
J.augenstein.

- Estructuras de datos y algoritmos

Autores: Alfred V. Aho, John E. Hopcroft, Jefrey D. Ullman

Páginas de internet:

- www.rincón.prog.metropoliglobal.com/cursosProg/ProgGen/
Estr_Datos /index.php?cap=6

- old.algoritmia.net/ed/grafos.htm

- www.lcc.uma.es/~galvez/ftp/tad/tadtema6.pdf

- inf.ufrgs.br/~nedel/inf0123/27-grfos.pdf

- www3.vji.es/~badia/ii13/docs/teoria/tema11.pdf

- www.ayc.unavarra.es/burusca/tema4.pdf