Saltar la navegación

3. Caminos mínimos

En busca del camino mínimo

En esta ocasión vamos a analizar las zonas del personal de Correos que recoge las cartas de los buzones o que lleva los paquetes a los puntos Citypaq. Este personal realiza su ruta usando vehículos motorizados, con lo cual el sentido en el que recorra las calles sí importa, puesto que habrá calles que sean dirección prohibida. Por esta razón el grafo que representa la situación es un grafo dirigido.

Reparto de correos
Emilio__. Calle aurora (CC BY-SA)

El objetivo es encontrar la ruta óptima que pase por todos los buzones y puntos Citypaq (camino Hamiltoniano), de manera que el vehículo motorizado realice el recorrido mínimo y así el consumo de combustible sea el menor posible. Para ello se pueden aplicar los algoritmos de Dijkstra o de Floyd-Warshall, por ejemplo.

Grafos hamiltonianos


Un grafo hamiltoniano es un tipo de grafo no dirigido que contiene un ciclo hamiltoniano.

Un ciclo hamiltoniano es un recorrido que visita cada vértice del grafo exactamente una vez, regresando al vértice de partida. En otras palabras, un grafo hamiltoniano es aquel en el que se puede trazar una ruta que pase por todos los vértices sin repetir ninguno y regrese al punto de partida

José Luis Muñoz Casado. Grafo hamiltoniano (CC BY-NC)

También se llama camino hamiltoniano del grafo a todo camino que contenga a todos los vértices del grafo.

Para grafos dirigidos, o digrafos, las definiciones correspondientes tienen en cuenta que las aristas están dirigidas.

  • Un camino dirigido en un digrafo es camino dirigido hamiltoniano si visita todos los vértices del digrafo sin repetir ninguno. 
  • Un ciclo dirigido hamiltoniano en un digrafo es un camino dirigido hamiltoniano que es ciclo.
  • El grafo dirigido es digrafo hamiltoniano si contiene un ciclo dirigido hamiltoniano.

Algunas consideraciones

  • Todos los grafos ciclos son hamiltonianos.
  • Los grafos completos con más de dos vértices son hamiltonianos.
  • Todos los sólidos platónicos (el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro), considerados como grafos, son hamiltonianos.
José Luis Muñoz Casado. Grafo dodecaedro (CC BY-NC)
  • Entre los grafos eulerianos los hay que son hamiltonianos y los hay que no lo son, y entre los grafos hamiltonianos los hay que son eulerianos y los hay que no lo son.

Condiciones necesarias

  • Un grafo hamiltoniano ha de ser conexo. 
  • Un grafo hamiltoniano no puede tener vértices de grado 1: en todos los vértices deben incidir al menos dos aristas, la de “entrada” y la de “salida”.

Algoritmo de Dijkstra

El algoritmo de Dijkstra o del camino mínimo es un algoritmo que sirve para determinar el camino más corto desde un nodo origen hasta los demás nodos de un grafo conexo, dirigido y ponderado dado.

  1. Consideremos el vértice o nodo origen \(V\) 
  2. Creamos una cadena, \(C=\{\}\), donde almacenar las distancias desde \(V\) a todos los nodos del grafo
  3. Inicializamos todas las distancias con un valor igual a infinito, ya que al principio esas distancias son desconocidas, a excepción de la distancia de \(V\) a \(V\), cuyo valor es 0
  4. Consideramos \(X=V\)
  5. Recorremos todos los nodos adyacentes a \(X\) que no estén marcados, \(V_i\)
  6. Calculamos la distancia candidata desde \(V\) a \(V_i\) pasando por \(X\) con la siguiente fórmula: \(d_c(V,V_i)=d(V,X)+d(X,V_i)\). Es decir, la distancia candidata desde \(V\) a \(V_i\) pasando por \(X\) es la distancia que actualmente hay en la cadena desde \(V\) a \(X\), más la distancia desde \(X\) hasta \(V_i\)
    1. Si la distancia candidata es menor que la distancia de \(V\) a \(V_i\) almacenada en la cadena, actualizamos la cadena con dicha distancia candidata
    2. Marcamos el nodo \(X\) como nodo completado
  7. Tomamos como próximo nodo aquel que esté a menor distancia de \(V\), según la cadena, \(C\), y que no esté marcado
  8. Volvemos al paso 4, mientras existan nodos no marcados.

Veamos un ejemplo con el siguiente grafo.

Grafo
José Luis Muñoz Casado. Grafo (CC BY-SA)

Paso 0

Creamos una tabla para recoger los datos.

Consideramos \(X = A \).

La distancia de \( A \) a \( A \) es cero.

Vértices Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Paso 7
A (0,A)
B
C
D
E
F
G

Paso 1

Los vértices adyacentes a \( A \) son \( B \) y \( C \). Calculamos sus distancias desde el vértice \( A \).

  • d(A,B) = 2. 
  • d(A,C)= 3. 

Se escribe en la tabla:

  • (2,A) para indicar que B está a distancia 2 desde A
  • (3,A) para indicar que C está a distancia 3 desde A
  • \( \infty \) para indicar que desde A no se puede ir a D, E, F ni a G
  • * Para indicar que el vértice A no se vuelve a evaluar
Vértices Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Paso 7
A (0,A) * * * * * *
B (2,A)
C (3,A)
D \( \infty \)
E \( \infty \)
F \( \infty \)
G \( \infty \)

Paso 2

Se elige el vértice con la menor distancia. En este caso B.

Desde B se puede ir a C, D y E

  • d(A,C) = d(A,B) + d(B,C) = 7
  • d(A,D) = d(A,B) + d(B,D) = 4
  • d(A,E) = d(A,B) + d(B,E) = 3

Se escribe en la tabla:

  • Para el vértice C tenemos dos datos (3,A) y (7,B). Se elige la menor distancia, es decir, (3,A)
  • (4,B) para indicar la distancia de A a D pasando por B
  • (3,B) para indicar la distancia de A a E pasando por B
  • \( \infty \) para indicar que desde A no se puede ir a F ni a G
  • * Para indicar que el vértice B no se vuelve a evaluar
Vértices Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Paso 7
A (0,A) * * * * * *
B (2,A) (2,A) * * * * *
C (3,A) (3,A) (7,B)
D \( \infty \) (4,B)
E \( \infty \) (3,B)
F \( \infty \) \( \infty \)
G \( \infty \) \( \infty \)
 
Paso 1 del algoritmo de Dijkstra
José Luis Muñoz Casado. Paso 2 del algoritmo de Dijkstra (CC BY-SA)

Paso 3

Se elige el vértice con la menor distancia. En este caso C.

Desde C se puede ir a D y F

  • d(A,D) = d(A,C) + d(C,D) = 7
  • d(A,F) = d(A,C) + d(C,F) = 5

Se escribe en la tabla:

  • Para el vértice D tenemos dos datos (4,B) y (7,B). Se elige la menor distancia, es decir, (4,B)
  • Desde C no se puede llegar a E, por tanto, dejamos el dato que había
  • (5,C) para indicar la distancia de A a F pasando por C
  • \( \infty \) para indicar que desde A no se puede ir a G
  • * Para indicar que el vértice C no se vuelve a evaluar.
Vértices Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Paso 7
A (0,A) * * * * * *
B (2,A) (2,A) * * * * *
C (3,A) (3,A) (3,A) * * * *
D \( \infty \) (4,B) (4,B) (7,B)
E \( \infty \) (3,B) (3,B)
F \( \infty \) \( \infty \) (5,C)
G \( \infty \) \( \infty \) \( \infty \)
Paso 2 del algoritmo de Dijkstra
José Luis Muñoz Casado. Paso 3 del algoritmo de Dijkstra (CC BY-SA)



Paso 4

Se elige el vértice con la menor distancia. En este caso, E.

Desde E se puede ir a D, F y G

  • d(A,D) = d(A,E) + d(E,D) = 6
  • d(A,F) = d(A,E) + d(E,F) = 6
  • d(A,G) = d(A,E) + d(E,G) = 8

Se escribe en la tabla:

  • Para el vértice E tenemos dos datos para llegar a D, (4,B) que ya teníamos y (6,E). Se elige la menor distancia, es decir, (5,C)
  • (8,E) para indicar la distancia de A a G pasando por E.
  • * Para indicar que el vértice E no se vuelve a evaluar.
Vértices Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Paso 7
A (0,A) * * * * * *
B (2,A) (2,A) * * * * *
C (3,A) (3,A) (3,A) * * * *
D \( \infty \) (4,B) (4,B) (7,B) (4,B)
E \( \infty \) (3,B) (3,B) (3,B) * * *
F \( \infty \) \( \infty \) (5,C) (5,C)
G \( \infty \) \( \infty \) \( \infty \) (8,E)
 
Paso 3 del algoritmo de Dijkstra
José Luis Muñoz Casado. Paso 4 del algoritmo de Dijkstra (CC BY-SA)

Paso 5

Se elige el vértice con la menor distancia. En este caso, D.

Desde D se puede ir a F 

  • d(A,F) = d(A,D) + d(D,F) = 5

Se escribe en la tabla:

  • (5,C) para indicar la distancia de A a F pasando por C o (5,D) para indicar la distancia de A a F pasando por D, ya que los dos caminos son iguales de largos. Nosotros vamos a elegir (5,C)
  • Desde D no se puede llegar a G, por tanto, dejamos el dato que había.
  • * Para indicar que el vértice D no se vuelve a evaluar.
Vértices Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Paso 7
A (0,A) * * * * * *
B (2,A) (2,A) * * * * *
C (3,A) (3,A) (3,A) * * * *
D \( \infty \) (4,B) (4,B) (7,B) (4,B) (4,B) * *
E \( \infty \) (3,B) (3,B) (3,B) * * *
F \( \infty \) \( \infty \) (5,C) (5,C) (5,C)
G \( \infty \) \( \infty \) \( \infty \) (8,E) (8,E)
 
Paso 5 del algoritmo de Dijkstra
José Luis Muñoz Casado. Paso 5 del algoritmo de Dijkstra (CC BY-SA)

Paso 6

Se elige el vértice con la menor distancia. En este caso, F.

Desde F se puede ir a G 

  • d(A,G) = d(A,F) + d(F,G) = 7

Se escribe en la tabla:

  • Para el vértice F tenemos dos datos para llegar a G, (8,E) que ya teníamos y (7,F). Se elige la menor distancia, es decir, (7,F)
  • * Para indicar que el vértice F no se vuelve a evaluar.
Vértices Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Paso 7
A (0,A) * * * * * *
B (2,A) (2,A) * * * * *
C (3,A) (3,A) (3,A) * * * *
D \( \infty \) (4,B) (4,B) (7,B) (4,B) (4,B) * *
E \( \infty \) (3,B) (3,B) (3,B) * * *
F \( \infty \) \( \infty \) (5,C) (5,C) (5,C) (5,C) *
G \( \infty \) \( \infty \) \( \infty \) (8,E) (8,E) (7,F)
 
Paso 6 del algoritmo de Dijkstra
José Luis Muñoz Casado. Paso 6 del algoritmo de Dijkstra (CC BY-SA)

Paso 7

Por último, marcamos el punto G

Vértices Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Paso 7
A (0,A) * * * * * *
B (2,A) (2,A) * * * * *
C (3,A) (3,A) (3,A) * * * *
D \( \infty \) (4,B) (4,B) (7,B) (4,B) (4,B) * *
E \( \infty \) (3,B) (3,B) (3,B) * * *
F \( \infty \) \( \infty \) (5,C) (5,C) (5,C) (5,C) *
G \( \infty \) \( \infty \) \( \infty \) (8,E) (8,E) (7,F) (7,F)
 
Paso 7 del algoritmo de Dijkstra
José Luis Muñoz Casado. Paso 7 del algoritmo de Dijkstra

Resultado

José Luis Muñoz Casado. Algoritmo de Dijkstra (CC BY-NC)

Algoritmo de Floyd-Warshall

El algoritmo de Floyd-Warshall es otro algoritmo que sirve para determinar el camino más corto entre cualesquiera dos nodos de un grafo conexo, dirigido y ponderado dado.

  1. Creamos dos matrices cuadradas con tantas filas y columnas como nodos, \(n\), tiene el grafo. Cada fila y cada columna se corresponderá con un nodo del grafo. Una será la matriz ponderada \(P\) y la otra será la matriz de recorridos \(R\) 
  2. En cada elemento de la matriz \(P\) escribimos los pesos de cada arista que une un nodo de una fila, con un nodo de una columna. Cuando no existe relación entre dos nodos su peso será infinito. Hay que tener en cuenta si el grafo es dirigido o no, de manera que puede ocurrir que la distancia de un nodo A a otro B sea una cantidad finita y la distancia de B a A sea infinito porque no se pueda recorrer la arista AB en el sentido de B a A. La diagonal de esta matriz siempre será nula, puesto que la distancia de un nodo a sí mismo es 0
  3. Inicialmente cada elemento de la matriz \(R\) se rellena con el nombre del nodo de su columna correspondiente.
  4. Nos situamos en la fila \(F_i\) y en la columna \(C_i\) de la matriz \(P\) \((i=1, ..., n)\)
  5. Buscamos el primer valor de la columna \(C_i\) que se corresponda con un peso de arista, es decir que no sea 0 ni infinito. Este elemento estará en la fila \(F_l\), \(l=1, ..., n; l\neq i\)
    1. Sumamos dicho valor a cada uno de los elementos de la fila \(F_i\) y obtenemos \(v_{ik}\), \(k=1,... ,n\).
    2. Si \(v_{ik}\) es menor que cualquier otro elemento de \(F_l\), sustituimos ese elemento por \(v_{ik}\)
  6. En la matriz \(R\) cambiamos los elementos que se corresponden con los elementos cambiados en la matriz \(P\) por el nombre del nodo desde el cual estamos evaluando, es decir el correspondiente a la fila \(F_i\) y a la columna \(C_i\)
  7. Repetimos los pasos 5 y 6 mientras haya elementos no nulos ni infinitos en la columna \(C_i\)
  8. Pasamos a la fila \(F_{i+1}\) y a la columna \(C_{i+1}\) y repetimos desde el paso 5 hasta que no queden más filas ni columnas por recorrer

Veamos un ejemplo con el siguiente grafo.

Grafo
José Luis Muñoz Casado. Grafo (CC BY-SA)

Paso 1

Se crean dos matrices (tablas) cuadradas con tantas filas y columnas como nodos tiene el grafo. Cada fila y cada columna se corresponderá con un nodo del grafo.

Una será la matriz ponderada, P, y la otra será la matriz de recorridos, R.

En cada elemento de la matriz P escribimos los pesos de cada arista que une un nodo de una fila con un nodo de una columna. Cuando no existe relación entre dos nodos su peso será infinito.

Hay que tener en cuenta si el grafo es dirigido o no, de manera que puede ocurrir que la distancia de un nodo A a otro B sea una cantidad finita y la distancia de B a A sea infinito porque no se pueda recorrer la arista AB en el sentido de B a A.  

La diagonal de esta matriz siempre será nula puesto que la distancia de un nodo a sí mismo es 0, la tabla P quedaría así:

V. A B C D E F G
A 0 2 3 \(\infty\) \(\infty\) \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 \(\infty\) 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0
Cada elemento de la matriz R se rellena con el nombre del nodo de su columna correspondiente, la tabla R quedaría así.
V. A B C D E F G
A A B C D E F G
B A B C D E F G
C A B C D E F G
D A B C D E F G
E A B C D E F G
F A B C D E F G
G A B C D E F G

Paso 2. Nodo A

Nos situamos en el nodo A, es decir en la primera fila y en la primera columna de la matriz P.

En la primera columna buscamos el primer elemento no nulo ni infinito (marcado en rojo)

V. A B C D E F G
A 0 2 3 \(\infty\) \(\infty\) \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 \(\infty\) 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

Sumamos ese valor a cada uno de los elementos de la primera fila y el resultado lo comparamos con los elementos correspondientes de la fila a la que pertenece el elemento no nulo ni infinito en el que nos hemos parado (en este caso los elementos de la fila 2) y la columna del elemento de la primera fila con el que estemos sumando. Si el valor resultante es menor que el elemento que hay en la fila y la columna correspondiente, sustituimos ese elemento por el nuevo valor.

En la matriz R cambiamos el elemento que se corresponde con el elemento cambiado en la matriz P por el nombre del nodo en el que estemos situados. En este caso el nodo A.

En este caso no cambia ningún elemento ni en P ni en R.

Paso 3. Nodo B

Pasamos al siguiente elemento no nulo ni infinito de la primera columna, marcado en rojo:

V. A B C D E F G
A 0 2 3 \(\infty\) \(\infty\) \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 \(\infty\) 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

Tampoco cambia ningún elemento, así que pasamos al nodo B, es decir a la segunda fila y la segunda columna:

V. A B C D E F G
A 0 2 3 \(\infty\) \(\infty\) \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 \(\infty\) 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

En la segunda columna buscamos el primer elemento no nulo ni infinito, marcado en rojo.

V. A B C D E F G
A 0 2 3 \(\infty\) \(\infty\) \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 \(\infty\) 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

2+2< \(\infty\), así que cambiamos \(\infty\) por 4 en la matriz de P y la D de la fila 1 y la columna 4 de R, por B, puesto que estamos en el nodo B.

V. A B C D E F G
A 0 2 3 4 \(\infty\) \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 \(\infty\) 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0
V A B C D E F G
A A B C B E F G
B A B C D E F G
C A B C D E F G
D A B C D E F G
E A B C D E F G
F A B C D E F G
G A B C D E F G

2+1<\(\infty\), así que cambiamos \(\infty\) por 3 en la matriz de P y la E de la fila 1 y la columna 5 de R, por B, puesto que estamos en el nodo B.

V. A B C D E F G
A 0 2 3 4 3 \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 \(\infty\) 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0
V. A B C D E F G
A A B C B B F G
B A B C D E F G
C A B C D E F G
D A B C D E F G
E A B C D E F G
F A B C D E F G
G A B C D E F G

Con este elemento ya no se puede realizar más cambios, pasamos al siguiente elemento no nulo ni infinito de la segunda columna, marcado en rojo:

V. A B C D E F G
A 0 2 3 4 3 \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 \(\infty\) 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

5+1<\(\infty\), así que cambiamos \(\infty\) por 6 en la matriz de P y la E de la fila 3 y la columna 5 de R, por B, puesto que seguimos en el nodo B.

V. A B C D E F G
A 0 2 3 4 3 \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0
V A B C D E F G
A A B C B B F G
B A B C D E F G
C A B C D B F G
D A B C D E F G
E A B C D E F G
F A B C D E F G
G A B C D E F G

Con este elemento ya no se puede realizar más cambios, pasamos al siguiente elemento no nulo ni infinito de la segunda columna, marcado en rojo:

V. A B C D E F G
A 0 2 3 4 3 \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D \(\infty\) 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

2+2<\(\infty\), así que cambiamos \(\infty\) por 4 en la matriz de P y la A de la fila 4 y la columna 1 de R, por B, puesto que seguimos en el nodo B.

V. A B C D E F G
A 0 2 3 4 3 \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0
V A B C D E F G
A A B C B B F G
B A B C D E F G
C A B C D B F G
D B B C D E F G
E A B C D E F G
F A B C D E F G
G A B C D E F G

Con este elemento ya no se puede realizar más cambios, así que pasamos al siguiente elemento no nulo ni infinito de la segunda columna, marcado en rojo:

Vért A B C D E F G
A 0 2 3 4 3 \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E \(\infty\) 1 \(\infty\) 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

1+2<\(\infty\), así que cambiamos \(\infty\) por 3 en la matriz de P y la A de la fila 5 y la columna 1 de R, por B, puesto que seguimos en el nodo B.

1+5<\(\infty\), así que cambiamos \(\infty\) por 6 en la matriz de P y la C de la fila 5 y la columna 3 de R, por B, puesto que seguimos en el nodo B.

Vért A B C D E F G
A 0 2 3 4 3 \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0
V A B C D E F G
A A B C B B F G
B A B C D E F G
C A B C D B F G
D B B C D E F G
E B B B D E F G
F A B C D E F G
G A B C D E F G

Paso 4. Nodo C

Pasamos al nodo C, es decir a la tercera fila y la tercera columna:

V. A B C D E F G
A 0 2 3 4 3 \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

En la tercera columna buscamos el primer elemento no nulo ni infinito, marcado en rojo.

V. A B C D E F G
A 0 2 3 4 3 \(\infty\) \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

3+2<\(\infty\), así que cambiamos \(\infty\) por 5 en la matriz de P y la C de la fila 1 y la columna 6 de R, por C, puesto que estamos en el nodo C.

V. A B C D E F G
A 0 2 3 4 3 5 \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0
V A B C D E F G
A A B C B B C G
B A B C D E F G
C A B C D B F G
D B B C D E F G
E B B B D E F G
F A B C D E F G
G A B C D E F G

Con este elemento ya no se puede realizar más cambios, así que pasamos al siguiente elemento no nulo ni infinito de la tercera columna, marcado en rojo:

V. A B C D E F G
A 0 2 3 4 3 5 \(\infty\)
B 2 0 5 2 1 \(\infty\) \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

5+2<\(\infty\), así que cambiamos \(\infty\) por 7 en la matriz de P y la C de la fila 2 y la columna 6 de R, por C, puesto que seguimos en el nodo C.

Vért A B C D E F G
A 0 2 3 4 3 5 \(\infty\)
B 2 0 5 2 1 7 \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0
V A B C D E F G
A A B C B B C G
B A B C D E C G
C A B C D B F G
D B B C D E F G
E B B B D E F G
F A B C D E F G
G A B C D E F G

Con este elemento ya no se puede realizar más cambios, así que pasamos al siguiente elemento no nulo ni infinito de la tercera columna, marcado en rojo:

Vért A B C D E F G
A 0 2 3 4 3 5 \(\infty\)
B 2 0 5 2 1 7 \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

Con este elemento no se puede realizar cambios, así que pasamos al siguiente elemento no nulo ni infinito de la tercera columna, marcado en naranja:

Vért A B C D E F G
A 0 2 3 4 3 5 \(\infty\)
B 2 0 5 2 1 7 \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

Con este elemento tampoco se puede realizar cambios así que pasamos al siguiente elemento no nulo ni infinito de la tercera columna, marcado en rojo:

Vért A B C D E F G
A 0 2 3 4 3 5 \(\infty\)
B 2 0 5 2 1 7 \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F \(\infty\) \(\infty\) 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0

2+3<\(\infty\), así que cambiamos \(\infty\) por 5 en la matriz de P y la A de la fila 6 y la columna 1 de R, por C, puesto que seguimos en el nodo C.

2+5<\(\infty\), así que cambiamos \(\infty\) por 7 en la matriz de P y la B de la fila 6 y la columna 2 de R, por C, puesto que seguimos en el nodo C.

Vért A B C D E F G
A 0 2 3 4 3 5 \(\infty\)
B 2 0 5 2 1 7 \(\infty\)
C 3 5 0 4 6 2 \(\infty\)
D 4 2 4 0 3 1 \(\infty\)
E 3 1 6 3 0 3 5
F 5 7 2 1 3 0 2
G \(\infty\) \(\infty\) \(\infty\) \(\infty\) 5 2 0
V A B C D E F G
A A B C B B C G
B A B C D E C G
C A B C D B F G
D B B C D E F G
E B B B D E F G
F C C C D E F G
G A B C D E F G

Paso 5. Así sucesivamente hasta el último nodo

De igual manera procedemos con el resto de vértices, D, E, F, G.

Resultado

Con este elemento no se puede realizar cambios y hemos terminado de aplicar el algoritmo. Las matrices finales son:

Vért A B C D E F G
A 0 2 3 4 3 5 7
B 2 0 5 2 1 3 5
C 3 5 0 3 5 2 4
D 4 2 3 0 3 1 3
E 3 1 5 3 0 3 5
F 5 3 2 1 3 0 2
G 7 5 4 3 5 2 0
V A B C D E F G
A A B C B B C F
B A B C D E D F
C A B C F F F F
D B B F D E F F
E B B F D E F G
F C D C D E F G
G F F F F E F G

Si queremos ir de A a G, la matriz de pesos nos dice que la distancia es 7 y la de recorridos nos dice que tenemos que hacerlo pasando por F.

Para ir de A a F, la matriz de pesos nos dice que la distancia es 5 y la matriz de recorridos nos dice que tenemos que hacerlo pasando por C.

Si queremos ir de B a G, la matriz de pesos nos dice que la distancia es 5 y la matriz de recorridos nos dice que tenemos que hacerlo pasando por

F. Para ir de B a F, la matriz de pesos nos dice que la distancia es 3 y la matriz de recorridos nos dice que tenemos que hacerlo pasando por D.

Si queremos representar en el grafo el camino más corto para ir desde A hasta cualquier nodo del grafo (lo que obtenemos con el algoritmo de Dijkstra) tenemos que representar los resultados obtenidos en la primera fila de las dos matrices:

  • AB: 2
  • AC: 3
  • AD: 4, pasando por B
  • AE: 3, pasando por B
  • AF: 5, pasando por C
  • AG: 7, pasando por F

Interpreta el algoritmo de Dijkstra

Observa la tabla y selecciona la opción correcta. Sólo una de las cuatro opciones es correcta.

2
%E9%B0%F3%E1%FB%F5%FC%F3%E6%E7%E0%F3%B0%A8%B0%B0%BE%B0%F3%E7%E6%FA%FD%E0%B0%A8%B0%B0%BE%B0%F3%E7%E6%FA%FD%E0%C4%FB%F6%F7%FD%B0%A8%B0%B0%BE%B0%E6%EB%E2%F7%D5%F3%FF%F7%B0%A8%B0%C3%E7%D7%EA%E6%B0%BE%B0%F7%FC%F6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%FB%F6%C4%FB%F6%F7%FD%B0%A8%B0%B0%BE%B0%E1%E6%F3%E0%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%FB%FC%E1%E6%E0%E7%F1%E6%FB%FD%FC%E1%D7%EA%F7%B0%A8%B0%B7%A1%D1%E2%B7%A1%D7%DD%F0%E1%F7%E0%E4%F3%B7%A0%A2%FE%F3%B7%A0%A2%E6%F3%F0%FE%F3%B7%A0%A2%EB%B7%A0%A2%E1%F7%FE%F7%F1%F1%FB%FD%FC%F3%B7%A0%A2%FE%F3%B7%A0%A2%FD%E2%F1%FB%B7%D4%A1%FC%B7%A0%A2%F1%FD%E0%E0%F7%F1%E6%F3%BC%B7%A0%A2%C1%B7%D4%A1%FE%FD%B7%A0%A2%E7%FC%F3%B7%A0%A2%F6%F7%B7%A0%A2%FE%F3%E1%B7%A0%A2%F1%E7%F3%E6%E0%FD%B7%A0%A2%FD%E2%F1%FB%FD%FC%F7%E1%B7%A0%A2%F7%E1%B7%A0%A2%F1%FD%E0%E0%F7%F1%E6%F3%BC%B7%A1%D1%BD%E2%B7%A1%D7%B0%BE%B0%FB%FC%E1%E6%E0%E7%F1%E6%FB%FD%FC%E1%B0%A8%B0%D7%FE%FB%F8%F3%B2%FE%F3%B2%E0%F7%E1%E2%E7%F7%E1%E6%F3%B2%F1%FD%E0%E0%F7%F1%E6%F3%B2%B0%BE%B0%E1%FA%FD%E5%DF%FB%FC%FB%FF%FB%E8%F7%B0%A8%F4%F3%FE%E1%F7%BE%B0%FD%E2%E6%FB%FD%FC%E1%C0%F3%FF%F6%FD%FC%B0%A8%E6%E0%E7%F7%BE%B0%F3%FC%E1%E5%F7%E0%E1%C0%F3%FF%F6%FD%FC%B0%A8%E6%E0%E7%F7%BE%B0%E1%FA%FD%E5%C1%FD%FE%E7%E6%FB%FD%FC%B0%A8%F4%F3%FE%E1%F7%BE%B0%E6%FB%FF%F7%C1%FA%FD%E5%C1%FD%FE%E7%E6%FB%FD%FC%B0%A8%A1%BE%B0%E7%E1%F7%DE%FB%E4%F7%E1%B0%A8%E6%E0%E7%F7%BE%B0%FC%E7%FF%F0%F7%E0%DE%FB%E4%F7%E1%B0%A8%A1%BE%B0%FB%E6%FB%FC%F7%E0%F3%E0%EB%B0%A8%E9%B0%E1%FA%FD%E5%D1%FE%E7%F7%B0%A8%F4%F3%FE%E1%F7%BE%B0%F1%FE%E7%F7%D5%F3%FF%F7%B0%A8%B0%B0%BE%B0%E2%F7%E0%F1%F7%FC%E6%F3%F5%F7%D1%FE%E7%F7%B0%A8%A6%A2%BE%B0%E1%FA%FD%E5%D1%FD%F6%F7%D3%F1%F1%F7%E1%E1%B0%A8%F4%F3%FE%E1%F7%BE%B0%F1%FD%F6%F7%D3%F1%F1%F7%E1%E1%B0%A8%B0%B0%BE%B0%FF%F7%E1%E1%F3%F5%F7%D1%FD%F6%F7%D3%F1%F1%F7%E1%E1%B0%A8%B0%B0%EF%BE%B0%E3%E7%F7%E1%E6%FB%FD%FC%E1%D5%F3%FF%F7%B0%A8%C9%E9%B0%E6%EB%E2%F7%B0%A8%A3%BE%B0%E6%FB%FF%F7%B0%A8%A0%BE%B0%FC%E7%FF%F0%F7%E0%DD%E2%E6%FB%FD%FC%E1%B0%A8%A6%BE%B0%EA%B0%A8%A2%BE%B0%EB%B0%A8%A2%BE%B0%F3%E7%E6%FA%FD%E0%B0%A8%B0%B0%BE%B0%F3%FE%E6%B0%A8%B0%B0%BE%B0%F1%E7%E1%E6%FD%FF%C1%F1%FD%E0%F7%B0%A8%A3%BE%B0%E7%E0%FE%B0%A8%B0%E0%F7%E1%FD%E7%E0%F1%F7%E1%BD%D3%FE%F5%FD%E0%FB%E6%FF%FD%CD%F6%F7%CD%D6%FB%F8%F9%E1%E6%E0%F3%CD%A3%BC%E2%FC%F5%B0%BE%B0%F3%E7%F6%FB%FD%B0%A8%B0%B0%BE%B0%E1%FD%E7%FC%F6%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%FF%F3%F5%F7%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F4%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E6%C1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F7%C6%F7%EA%E6%B0%A8%B0%B0%BE%B0%E3%E7%F7%EA%E6%FB%FD%FC%B0%A8%B0%D7%FE%B2%F1%F3%FF%FB%FC%FD%B2%FFs%E1%B2%F1%FD%E0%E6%FD%B2%E2%F3%E0%F3%B2%FB%E0%B2%F6%F7%B2%D3%B2%F3%B2%D7%B2%F7%E1%B0%BE%B0%FD%E2%E6%FB%FD%FC%E1%B0%A8%C9%B0%DB%E0%B2%F6%F7%B2%D3%B2%F3%B2%D0%BE%B2%E3%E7%F7%B2%F7%E1%E6s%FC%B2%F3%B2%F6%FB%E1%E6%F3%FC%F1%FB%F3%B2%A3%B2%EB%B2%FE%E7%F7%F5%FD%B2%F6%F7%B2%D0%B2%F3%B2%D7%B2%E3%E7%F7%B2%F7%E1%E6s%FC%B2%F3%B2%F6%FB%E1%E6%F3%FC%F1%FB%F3%B2%A0%B0%BE%B0%DB%E0%B2%F6%F7%B2%D3%B2%F3%B2%D7%B2%E3%E7%F7%B2%F7%E1%E6s%FC%B2%F3%B2%F6%FB%E1%E6%F3%FC%F1%FB%F3%B2%A1%B0%BE%B0%DB%E0%B2%F6%F7%B2%D3%B2%F3%B2%D0%B2%E3%E7%F7%B2%F7%E1%E6s%FC%B2%F3%B2%F6%FB%E1%E6%F3%FC%F1%FB%F3%B2%A1%B2%FD%B2%A3%B0%BE%B0%DB%E0%B2%F6%F7%B2%D3%B2%F3%B2%D1%B2%E3%E7%F7%B2%F7%E1%E6s%FC%B2%F3%B2%F6%FB%E1%E6%F3%FC%F1%FB%F3%B2%A0%B2%EB%B2%FE%E7%F7%F5%FD%B2%F6%F7%B2%D1%B2%F3%B2%D7%B2%E3%E7%F7%B2%F7%E1%E6s%FC%B2%F3%B2%F6%FB%E1%E6%F3%FC%F1%FB%F3%B2%A3%B0%CF%BE%B0%E1%FD%FE%E7%E6%FB%FD%FC%B0%A8%A2%BE%B0%FF%E1%F5%DA%FB%E6%B0%A8%B0%B0%BE%B0%FF%E1%F5%D7%E0%E0%FD%E0%B0%A8%B0%B0%EF%BE%E9%B0%E6%EB%E2%F7%B0%A8%A3%BE%B0%E6%FB%FF%F7%B0%A8%A0%BE%B0%FC%E7%FF%F0%F7%E0%DD%E2%E6%FB%FD%FC%E1%B0%A8%A6%BE%B0%EA%B0%A8%A2%BE%B0%EB%B0%A8%A2%BE%B0%F3%E7%E6%FA%FD%E0%B0%A8%B0%B0%BE%B0%F3%FE%E6%B0%A8%B0%B0%BE%B0%F1%E7%E1%E6%FD%FF%C1%F1%FD%E0%F7%B0%A8%A3%BE%B0%E7%E0%FE%B0%A8%B0%E0%F7%E1%FD%E7%E0%F1%F7%E1%BD%D3%FE%F5%FD%E0%FB%E6%FF%FD%CD%F6%F7%CD%D6%FB%F8%F9%E1%E6%E0%F3%CD%A3%BC%E2%FC%F5%B0%BE%B0%F3%E7%F6%FB%FD%B0%A8%B0%B0%BE%B0%E1%FD%E7%FC%F6%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%FF%F3%F5%F7%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F4%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E6%C1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F7%C6%F7%EA%E6%B0%A8%B0%B0%BE%B0%E3%E7%F7%EA%E6%FB%FD%FC%B0%A8%B0%D7%FE%B2%F1%F3%FF%FB%FC%FD%B2%FFs%E1%B2%F1%FD%E0%E6%FD%B2%E2%F3%E0%F3%B2%FB%E0%B2%F6%F7%B2%D6%B2%F3%B2%D4%B2%F7%E1%A8%B0%BE%B0%FD%E2%E6%FB%FD%FC%E1%B0%A8%C9%B0%D7%E1%B2%F6%FB%E0%F7%F1%E6%FD%B2%EB%B2%FF%FB%F6%F7%B2%A7%B0%BE%B0%DA%F3%EB%B2%E3%E7%F7%B2%E2%F3%E1%F3%E0%B2%E2%FD%E0%B2%D3%B2%EB%B2%FF%FB%F6%F7%B2%A7%B0%BE%B0%D7%E1%B2%F6%FB%E0%F7%F1%E6%FD%B2%EB%B2%FF%FB%F6%F7%B2%A0%B0%BE%B0%DA%F3%EB%B2%E3%E7%F7%B2%E2%F3%E1%F3%E0%B2%E2%FD%E0%B2%E6%FD%F6%FD%E1%B2%FE%FD%E1%B2%FC%FD%F6%FD%E1%B2%EB%B2%FF%FB%F6%F7%B2%A7%B0%CF%BE%B0%E1%FD%FE%E7%E6%FB%FD%FC%B0%A8%A0%BE%B0%FF%E1%F5%DA%FB%E6%B0%A8%B0%B0%BE%B0%FF%E1%F5%D7%E0%E0%FD%E0%B0%A8%B0%B0%EF%BE%E9%B0%E6%EB%E2%F7%B0%A8%A3%BE%B0%E6%FB%FF%F7%B0%A8%A0%BE%B0%FC%E7%FF%F0%F7%E0%DD%E2%E6%FB%FD%FC%E1%B0%A8%A6%BE%B0%EA%B0%A8%A2%BE%B0%EB%B0%A8%A2%BE%B0%F3%E7%E6%FA%FD%E0%B0%A8%B0%B0%BE%B0%F3%FE%E6%B0%A8%B0%B0%BE%B0%F1%E7%E1%E6%FD%FF%C1%F1%FD%E0%F7%B0%A8%A3%BE%B0%E7%E0%FE%B0%A8%B0%E0%F7%E1%FD%E7%E0%F1%F7%E1%BD%D3%FE%F5%FD%E0%FB%E6%FF%FD%CD%F6%F7%CD%D6%FB%F8%F9%E1%E6%E0%F3%CD%A3%BC%E2%FC%F5%B0%BE%B0%F3%E7%F6%FB%FD%B0%A8%B0%B0%BE%B0%E1%FD%E7%FC%F6%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%FF%F3%F5%F7%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F4%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E6%C1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F7%C6%F7%EA%E6%B0%A8%B0%B0%BE%B0%E3%E7%F7%EA%E6%FB%FD%FC%B0%A8%B0%D7%FE%B2%F1%F3%FF%FB%FC%FD%B2%FFs%E1%B2%F1%FD%E0%E6%FD%B2%E2%F3%E0%F3%B2%FB%E0%B2%F6%F7%B2%D1%B2%F3%B2%D6%B2%F7%E1%A8%B0%BE%B0%FD%E2%E6%FB%FD%FC%E1%B0%A8%C9%B0%D7%E1%B2%F6%FB%E0%F7%F1%E6%FD%B2%EB%B2%FF%FB%F6%F7%B2%A1%B0%BE%B0%D7%E1%B2%F6%FB%E0%F7%F1%E6%FD%B2%EB%B2%FF%FB%F6%F7%B2%A3%B0%BE%B0%DA%F3%EB%B2%E3%E7%F7%B2%E2%F3%E1%F3%E0%B2%E2%FD%E0%B2%D0%B2%EB%B2%FF%FB%F6%F7%B2%A3%B0%BE%B0%DA%F3%EB%B2%E3%E7%F7%B2%E2%F3%E1%F3%E0%B2%E2%FD%E0%B2%D3%BE%B2%D0%B2%EB%B2%D1%B2%EB%B2%FF%FB%F6%F7%B2%A1%B0%CF%BE%B0%E1%FD%FE%E7%E6%FB%FD%FC%B0%A8%A3%BE%B0%FF%E1%F5%DA%FB%E6%B0%A8%B0%B0%BE%B0%FF%E1%F5%D7%E0%E0%FD%E0%B0%A8%B0%B0%EF%BE%E9%B0%E6%EB%E2%F7%B0%A8%A3%BE%B0%E6%FB%FF%F7%B0%A8%A0%BE%B0%FC%E7%FF%F0%F7%E0%DD%E2%E6%FB%FD%FC%E1%B0%A8%A6%BE%B0%EA%B0%A8%A2%BE%B0%EB%B0%A8%A2%BE%B0%F3%E7%E6%FA%FD%E0%B0%A8%B0%B0%BE%B0%F3%FE%E6%B0%A8%B0%B0%BE%B0%F1%E7%E1%E6%FD%FF%C1%F1%FD%E0%F7%B0%A8%A3%BE%B0%E7%E0%FE%B0%A8%B0%E0%F7%E1%FD%E7%E0%F1%F7%E1%BD%D3%FE%F5%FD%E0%FB%E6%FF%FD%CD%F6%F7%CD%D6%FB%F8%F9%E1%E6%E0%F3%CD%A3%BC%E2%FC%F5%B0%BE%B0%F3%E7%F6%FB%FD%B0%A8%B0%B0%BE%B0%E1%FD%E7%FC%F6%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%FF%F3%F5%F7%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F4%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E6%C1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F7%C6%F7%EA%E6%B0%A8%B0%B0%BE%B0%E3%E7%F7%EA%E6%FB%FD%FC%B0%A8%B0%D7%FE%B2%FC%FD%F6%FD%B2%FD%E0%FB%F5%F7%FC%B2%F7%E1%B2%D3%B2%EB%B2%FE%FD%E1%B2%FC%FD%F6%FD%E1%B2%F4%FB%FC%F3%FE%F7%E1%B2%E1%FD%FC%A8%B0%BE%B0%FD%E2%E6%FB%FD%FC%E1%B0%A8%C9%B0%D0%B2%EB%B2%D6%B0%BE%B0%D6%B2%EB%B2%D4%B0%BE%B0%D7%B2%EB%B2%D4%B0%BE%B0%D1%B2%EB%B2%D6%B0%CF%BE%B0%E1%FD%FE%E7%E6%FB%FD%FC%B0%A8%A0%BE%B0%FF%E1%F5%DA%FB%E6%B0%A8%B0%B0%BE%B0%FF%E1%F5%D7%E0%E0%FD%E0%B0%A8%B0%B0%EF%BE%E9%B0%E6%EB%E2%F7%B0%A8%A3%BE%B0%E6%FB%FF%F7%B0%A8%A0%BE%B0%FC%E7%FF%F0%F7%E0%DD%E2%E6%FB%FD%FC%E1%B0%A8%A6%BE%B0%EA%B0%A8%A2%BE%B0%EB%B0%A8%A2%BE%B0%F3%E7%E6%FA%FD%E0%B0%A8%B0%B0%BE%B0%F3%FE%E6%B0%A8%B0%B0%BE%B0%F1%E7%E1%E6%FD%FF%C1%F1%FD%E0%F7%B0%A8%A3%BE%B0%E7%E0%FE%B0%A8%B0%E0%F7%E1%FD%E7%E0%F1%F7%E1%BD%D3%FE%F5%FD%E0%FB%E6%FF%FD%CD%F6%F7%CD%D6%FB%F8%F9%E1%E6%E0%F3%CD%A0%BC%E2%FC%F5%B0%BE%B0%F3%E7%F6%FB%FD%B0%A8%B0%B0%BE%B0%E1%FD%E7%FC%F6%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%FF%F3%F5%F7%C4%FB%F6%F7%FD%B0%A8%A3%BE%B0%FB%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F4%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%E6%C1%FB%FE%F7%FC%E6%C4%FB%F6%F7%FD%B0%A8%A2%BE%B0%F7%C6%F7%EA%E6%B0%A8%B0%B0%BE%B0%E3%E7%F7%EA%E6%FB%FD%FC%B0%A8%B0%DE%F3%B2%E1%FB%F5%E7%FB%F7%FC%E6%F7%B2%E6%F3%F0%FE%F3%B2%FF%E7%F7%E1%E6%E0%F3%B2%FD%E6%E0%F3%B2%E1%FD%FE%E7%F1%FBa%FC%B2%F6%F7%FE%B2%E2%E0%FD%F0%FE%F7%FF%F3%B2%F6%F7%FE%B2%F1%F3%FF%FB%FC%FD%B2%FF%7F%FC%FB%FF%FD%B2%E7%E6%FB%FE%FB%E8%F3%FC%F6%FD%B2%F7%FE%B2%F3%FE%F5%FD%E0%FB%E6%FF%FD%B2%F6%F7%B2%D6%FB%F8%F9%E1%E6%E0%F3%B0%BE%B0%FD%E2%E6%FB%FD%FC%E1%B0%A8%C9%B0%DB%FF%E2%FD%E1%FB%F0%FE%F7%BE%B2%FE%F3%B2%E1%FD%FE%E7%F1%FBa%FC%B2%F7%E1%B2h%FC%FB%F1%F3%B0%BE%B0%C2%E7%F7%F6%F7%B2%E1%F7%E0%BE%B2%E2%F7%E0%FD%B2%FC%FD%B2%FE%FD%B2%E2%FD%F6%F7%FF%FD%E1%B2%F3%E1%F7%F5%E7%E0%F3%E0%B2%E1%FB%FC%B2%E4%F7%E0%B2%F7%FE%B2%F5%E0%F3%F4%FD%B0%BE%B0%DB%FF%E2%FD%E1%FB%F0%FE%F7%BE%B2%FE%F3%B2%E1%FD%FE%E7%F1%FBa%FC%B2%E6%FB%F7%FC%F7%B2%E3%E7%F7%B2%E1%F3%FE%FB%E0%B2%F4%FD%E0%FF%F3%FC%F6%FD%B2%E7%FC%F3%B2%u208E%F7%E1%F1%F3%FE%F7%E0%F3%u208F%B0%BE%B0%C2%E7%F7%F6%F7%B2%E1%F7%E0%BE%B2%FA%F3%EB%B2%F6%FD%E1%B2%F1%F3%FF%FB%FC%FD%E1%B2%F1%FD%FC%B2%FE%F3%B2%FF%FB%E1%FF%F3%B2%FE%FD%FC%F5%FB%E6%E7%F6%B2%E3%E7%F7%B2%FC%FD%E1%B2%FE%FE%F7%E4%F3%FC%B2%F3%FE%B2%FF%FB%E1%FF%FD%B2%FF%FD%F6%FD%B2%EB%BE%B2%F6%F7%E2%F7%FC%F6%FB%F7%FC%F6%FD%B2%F6%F7%B2%F1%E7%F3%FE%B2%F7%FE%FB%F8%F3%FF%FD%E1%BE%B2%FD%F0%E6%F7%FC%F6%E0%F7%FF%FD%E1%B2%E7%FC%F3%B2%E1%FD%FE%E7%F1%FBa%FC%B2%E7%B2%FD%E6%E0%F3%BC%B0%CF%BE%B0%E1%FD%FE%E7%E6%FB%FD%FC%B0%A8%A1%BE%B0%FF%E1%F5%DA%FB%E6%B0%A8%B0%B0%BE%B0%FF%E1%F5%D7%E0%E0%FD%E0%B0%A8%B0%B0%EF%CF%BE%B0%FB%E1%C1%F1%FD%E0%FF%B0%A8%A2%BE%B0%E6%F7%EA%E6%D0%E7%E6%E6%FD%FC%C1%F1%FD%E0%FF%B0%A8%B0%D5%E7%F3%E0%F6%F3%E0%B2%FE%F3%B2%E2%E7%FC%E6%E7%F3%F1%FBa%FC%B0%BE%B0%E0%F7%E2%F7%F3%E6%D3%F1%E6%FB%E4%FB%E6%EB%B0%A8%F4%F3%FE%E1%F7%BE%B0%E6%FB%E6%FE%F7%B0%A8%B0%B0%BE%B0%F1%E7%E1%E6%FD%FF%C1%F1%FD%E0%F7%B0%A8%F4%F3%FE%E1%F7%BE%B0%E6%F7%EA%E6%D3%F4%E6%F7%E0%B0%A8%B0%B0%BE%B0%E6%F7%EA%E6%D4%F7%F7%F6%D0%F3%F1%F9%B0%A8%B0%B0%BE%B0%F5%F3%FF%F7%DF%FD%F6%F7%B0%A8%A3%BE%B0%F4%F7%F7%F6%D0%F3%F1%F9%B0%A8%F4%F3%FE%E1%F7%BE%B0%E2%F7%E0%F1%F7%FC%E6%F3%F8%F7%D4%D0%B0%A8%A3%A2%A2%BE%B0%E4%F7%E0%E1%FB%FD%FC%B0%A8%A0%BE%B0%F1%E7%E1%E6%FD%FF%DF%F7%E1%E1%F3%F5%F7%E1%B0%A8%F4%F3%FE%E1%F7%BE%B0%E2%F7%E0%F1%F7%FC%E6%F3%F8%F7%C3%E7%F7%E1%E6%FB%FD%FC%E1%B0%A8%A3%A2%A2%BE%B0%FF%E1%F5%E1%B0%A8%E9%B0%FF%E1%F5%C1%E6%F3%E0%E6%D5%F3%FF%F7%B0%A8%B0%C2%E7%FE%E1%F7%B2%F3%E3%E7%7F%B2%E2%F3%E0%F3%B2%F7%FF%E2%F7%E8%F3%E0%B0%BE%B0%FF%E1%F5%C1%E7%F0%FF%FB%E6%B0%A8%B0%D7%FC%E4%FB%F3%E0%B0%BE%B0%FF%E1%F5%D1%FE%E7%F7%B0%A8%B03%D5%F7%FC%FB%F3%FE%B3%B2%DE%F3%B2%E2%FB%E1%E6%F3%B2%F7%E1%A8%B0%BE%B0%FF%E1%F5%DC%F7%E5%D5%F3%FF%F7%B0%A8%B0%C2%E7%FE%E1%F7%B2%F3%E3%E7%7F%B2%E2%F3%E0%F3%B2%F7%FF%E2%F7%E8%F3%E0%B2%FD%E6%E0%F3%B2%E2%F3%E0%E6%FB%F6%F3%B0%BE%B0%FF%E1%F5%D1%FD%F6%F7%D3%F1%F1%F7%E1%E1%B0%A8%B0%D1a%F6%FB%F5%FD%B2%F6%F7%B2%F3%F1%F1%F7%E1%FD%B0%BE%B0%FF%E1%F5%DB%FC%F4%FD%E0%FF%F3%E6%FB%FD%FC%DE%FD%FD%F9%FB%FC%F5%B0%A8%B03%D5%F7%FC%FB%F3%FE%B3%B2%DE%F3%B2%FB%FC%F4%FD%E0%FF%F3%F1%FBa%FC%B2%E3%E7%F7%B2%F7%E1%E6%F3%F0%F3%B2%F0%E7%E1%F1%F3%FC%F6%FD%B0%BE%B0%FF%E1%F5%C2%FE%F3%EB%C1%E6%F3%E0%E6%B0%A8%B0%C2%E7%FE%E1%F7%B2%F3%E3%E7%7F%B2%E2%F3%E0%F3%B2%F8%E7%F5%F3%E0%B0%BE%B0%FF%E1%F5%D7%E0%E0%FD%E0%E1%B0%A8%B0%D7%E0%E0%FD%E0%F7%E1%B0%BE%B0%FF%E1%F5%DA%FB%E6%E1%B0%A8%B0%D3%F1%FB%F7%E0%E6%FD%E1%B0%BE%B0%FF%E1%F5%C1%F1%FD%E0%F7%B0%A8%B0%C2%E7%FC%E6%E7%F3%F1%FBa%FC%B0%BE%B0%FF%E1%F5%DF%FB%FC%FB%FF%FB%E8%F7%B0%A8%B0%DF%FB%FC%FB%FF%FB%E8%F3%E0%B0%BE%B0%FF%E1%F5%DF%F3%EA%FB%FF%FB%E8%F7%B0%A8%B0%DF%F3%EA%FB%FF%FB%E8%F3%E0%B0%BE%B0%FF%E1%F5%C6%FB%FF%F7%B0%A8%B0%C6%FB%F7%FF%E2%FD%B2%E2%FD%E0%B2%E2%E0%F7%F5%E7%FC%E6%F3%B0%BE%B0%FF%E1%F5%DE%FB%E4%F7%B0%A8%B0%C4%FB%F6%F3%B0%BE%B0%FF%E1%F5%D4%E7%FE%FE%C1%F1%E0%F7%F7%FC%B0%A8%B0%C2%F3%FC%E6%F3%FE%FE%F3%B2%D1%FD%FF%E2%FE%F7%E6%F3%B0%BE%B0%FF%E1%F5%D7%EA%FB%E6%D4%E7%FE%FE%C1%F1%E0%F7%F7%FC%B0%A8%B0%C1%F3%FE%FB%E0%B2%F6%F7%FE%B2%FF%FD%F6%FD%B2%E2%F3%FC%E6%F3%FE%FE%F3%B2%F1%FD%FF%E2%FE%F7%E6%F3%B0%BE%B0%FF%E1%F5%DC%E7%FF%C3%E7%F7%E1%E6%FB%FD%FC%E1%B0%A8%B0%DCh%FF%F7%E0%FD%B2%F6%F7%B2%E2%E0%F7%F5%E7%FC%E6%F3%E1%B0%BE%B0%FF%E1%F5%DC%FD%DB%FF%F3%F5%F7%B0%A8%B0%C2%E0%F7%F5%E7%FC%E6%F3%B2%E1%FB%FC%B2%FB%FFs%F5%F7%FC%F7%E1%B0%BE%B0%FF%E1%F5%D1%FD%FD%FE%B0%A8%B03%D0%FB%F7%FC%B3%B0%BE%B0%FF%E1%F5%DE%FD%E1%F7%C6%B0%A8%B0%DA%F3%B2%E2%F7%E0%F6%FB%F6%FD%B2%A1%A1%A2%B2%E2%E7%FC%E6%FD%E1%B0%BE%B0%FF%E1%F5%DE%FD%E1%F7%DE%FB%E4%F7%B0%A8%B0%DA%F3%B2%E2%F7%E0%F6%FB%F6%FD%B2%E7%FC%F3%B2%E4%FB%F6%F3%B0%BE%B0%FF%E1%F5%DE%FD%E1%E6%DE%FB%E4%F7%E1%B0%A8%B03%DA%F3%B2%E2%F7%E0%F6%FB%F6%FD%B2%E6%FD%F6%F3%E1%B2%E1%E7%E1%B2%E4%FB%F6%F3%E1%B3%B0%BE%B0%FF%E1%F5%D3%FE%FE%C3%E7%F7%E1%E6%FB%FD%FC%E1%B0%A8%B03%D1%FD%FF%E2%FE%F7%E6%F3%F6%F3%E1%B2%FE%F3%E1%B2%E2%E0%F7%F5%E7%FC%E6%F3%E1%B3%B0%BE%B0%FF%E1%F5%C1%E7%F1%F1%F7%E1%E1%F7%E1%B0%A8%B03%D1%FD%E0%E0%F7%F1%E6%FD%B3%B2%EE%B23%D7%EA%F1%F7%FE%F7%FC%E6%F7%B3%B2%EE%B23%D5%F7%FC%FB%F3%FE%B3%B2%EE%B23%DF%E7%EB%B2%F0%FB%F7%FC%B3%B2%EE%B23%C2%F7%E0%F4%F7%F1%E6%FD%B3%B0%BE%B0%FF%E1%F5%D4%F3%FB%FE%E7%E0%F7%E1%B0%A8%B03%DC%FD%B2%F7%E0%F3%B2%F7%E1%FD%B3%B2%EE%B23%DB%FC%F1%FD%E0%E0%F7%F1%E6%FD%B3%B2%EE%B23%DC%FD%B2%F7%E1%B2%F1%FD%E0%E0%F7%F1%E6%FD%B3%B2%EE%B23%DE%FD%B2%E1%F7%FC%E6%FB%FF%FD%E1%B3%B2%EE%B23%D7%E0%E0%FD%E0%B3%B0%BE%B0%FF%E1%F5%C1%F1%FD%E0%F7%C1%F1%FD%E0%FF%B0%A8%B0%DE%F3%B2%E2%E7%FC%E6%E7%F3%F1%FBa%FC%B2%FC%FD%B2%E1%F7%B2%E2%E7%F7%F6%F7%B2%F5%E7%F3%E0%F6%F3%E0%B2%E2%FD%E0%E3%E7%F7%B2%F7%E1%E6%F3%B2%E2s%F5%FB%FC%F3%B2%FC%FD%B2%F4%FD%E0%FF%F3%B2%E2%F3%E0%E6%F7%B2%B2%F6%F7%B2%E7%FC%B2%E2%F3%E3%E7%F7%E6%F7%B2%C1%D1%DD%C0%DF%BC%B0%BE%B0%FF%E1%F5%C3%E7%F7%E1%E6%FB%FD%FC%B0%A8%B0%C2%E0%F7%F5%E7%FC%E6%F3%B0%BE%B0%FF%E1%F5%DD%FC%FE%EB%C1%F3%E4%F7%C1%F1%FD%E0%F7%B0%A8%B03%C1a%FE%FD%B2%E2%E7%F7%F6%F7%B2%F5%E7%F3%E0%F6%F3%E0%B2%FE%F3%B2%E2%E7%FC%E6%E7%F3%F1%FBa%FC%B2%E7%FC%F3%B2%E4%F7%E8%B3%B0%BE%B0%FF%E1%F5%DD%FC%FE%EB%C1%F3%E4%F7%B0%A8%B0%C1a%FE%FD%B2%E2%E7%F7%F6%F7%B2%F5%E7%F3%E0%F6%F3%E0%B2%E7%FC%F3%B2%E4%F7%E8%B0%BE%B0%FF%E1%F5%DB%FC%F4%FD%E0%FF%F3%E6%FB%FD%FC%B0%A8%B0%DB%FC%F4%FD%E0%FF%F3%F1%FBa%FC%B0%BE%B0%FF%E1%F5%D3%E7%E6%FA%FD%E0%B0%A8%B0%D3%E7%E6%FD%E0%7F%F3%B0%BE%B0%FF%E1%F5%DD%FC%FE%EB%C1%F3%E4%F7%D3%E7%E6%FD%B0%A8%B0%C1%E7%B2%E2%E7%FC%E6%E7%F3%F1%FBa%FC%B2%E1%F7%B2%F5%E7%F3%E0%F6%F3%E0s%B2%F6%F7%E1%E2%E7%7B%E1%B2%F6%F7%B2%F1%F3%F6%F3%B2%E2%E0%F7%F5%E7%FC%E6%F3%BC%B2%C1a%FE%FD%B2%E2%E7%F7%F6%F7%B2%F8%E7%F5%F3%E0%B2%E7%FC%F3%B2%E4%F7%E8%BC%B0%BE%B0%FF%E1%F5%C1%F3%E4%F7%D3%E7%E6%FD%B0%A8%B0%C1%E7%B2%E2%E7%FC%E6%E7%F3%F1%FBa%FC%B2%E1%F7%B2%F5%E7%F3%E0%F6%F3%E0s%B2%F3%E7%E6%FD%FFs%E6%FB%F1%F3%FF%F7%FC%E6%F7%B2%F6%F7%E1%E2%E7%7B%E1%B2%F6%F7%B2%F1%F3%F6%F3%B2%E2%E0%F7%F5%E7%FC%E6%F3%BC%B0%BE%B0%FF%E1%F5%CB%FD%E7%C1%F1%FD%E0%F7%B0%A8%B0%C1%E7%B2%E2%E7%FC%E6%E7%F3%F1%FBa%FC%B0%BE%B0%FF%E1%F5%C1%F7%E4%F7%E0%F3%FE%C1%F1%FD%E0%F7%B0%A8%B0%C2%E7%F7%F6%F7%B2%F5%E7%F3%E0%F6%F3%E0%B2%FE%F3%B2%E2%E7%FC%E6%E7%F3%F1%FBa%FC%B2%E6%F3%FC%E6%F3%E1%B2%E4%F7%F1%F7%E1%B2%F1%FD%FF%FD%B2%E3%E7%FB%F7%E0%F3%B0%BE%B0%FF%E1%F5%CB%FD%E7%DE%F3%E1%E6%C1%F1%FD%E0%F7%B0%A8%B0%DE%F3%B2h%FE%E6%FB%FF%F3%B2%E2%E7%FC%E6%E7%F3%F1%FBa%FC%B2%F5%E7%F3%E0%F6%F3%F6%F3%B2%F7%E1%B0%BE%B0%FF%E1%F5%D3%F1%E6%FB%E6%EB%D1%FD%FF%E2%FE%EB%B0%A8%B0%CB%F3%B2%FA%F3%B2%E0%F7%F3%FE%FB%E8%F3%F6%FD%B2%F7%E1%E6%F3%B2%F3%F1%E6%FB%E4%FB%F6%F3%F6%BC%B0%BE%B0%FF%E1%F5%C2%FE%F3%EB%C1%F7%E4%F7%E0%F3%FE%C6%FB%FF%F7%E1%B0%A8%B0%C2%E7%F7%F6%F7%B2%E0%F7%F3%FE%FB%E8%F3%E0%B2%F7%E1%E6%F3%B2%F3%F1%E6%FB%E4%FB%F6%F3%F6%B2%F1%E7%F3%FC%E6%F3%E1%B2%E4%F7%F1%F7%E1%B2%E3%E7%FB%F7%E0%F3%B0%BE%B0%FF%E1%F5%C6%E0%EB%D3%F5%F3%FB%FC%B0%A8%B0%DC%F7%F1%F7%E1%FB%E6%F3%B2%F3%FE%B2%FF%F7%FC%FD%E1%B2%E7%FC%B2%B7%E1%B7%B2%F6%F7%B2%E0%F7%E1%E2%E7%F7%E1%E6%F3%E1%B2%F1%FD%E0%E0%F7%F1%E6%F3%E1%B2%E2%F3%E0%F3%B2%F1%FD%FC%E1%F7%F5%E7%FB%E0%B2%FE%F3%B2%FB%FC%F4%FD%E0%FF%F3%F1%FBa%FC%BC%B2%C4%E7%F7%FE%E4%F3%B2%F3%B2%FB%FC%E6%F7%FC%E6%F3%E0%FE%FD%BC%B0%BE%B0%FF%E1%F5%C4%FB%F6%F7%FD%DB%FC%E6%E0%FD%B0%A8%B0%C4%7F%F6%F7%FD%B2%F6%F7%B2%FB%FC%E6%E0%FD%F6%E7%F1%F1%FBa%FC%B0%BE%B0%FF%E1%F5%D1%FE%FD%E1%F7%B0%A8%B0%D1%F7%E0%E0%F3%E0%B0%BE%B0%FF%E1%F5%DD%E2%E6%FB%FD%FC%B0%A8%B0%DD%E2%F1%FBa%FC%B0%BE%B0%FF%E1%F5%C7%E1%F7%D4%E7%FE%DB%FC%F4%FD%E0%FF%F3%E6%FB%FD%FC%B0%A8%B0%F7%B2%FB%FC%F4%FD%E0%FF%F3%F1%FBa%FC%B2%E3%E7%F7%B2%E1%F7%E0s%B2%FF%E7%EB%B2h%E6%FB%FE%B0%BE%B0%FF%E1%F5%DE%FD%F3%F6%FB%FC%F5%B0%A8%B0%D1%F3%E0%F5%F3%FC%F6%FD%BC%B2%D7%E1%E2%F7%E0%F7%BE%B2%E2%FD%E0%B2%F4%F3%E4%FD%E0%BC%BC%BC%B0%BE%B0%FF%E1%F5%C2%FD%FB%FC%E6%E1%B0%A8%B0%E2%E7%FC%E6%FD%E1%B0%BE%B0%FF%E1%F5%D3%E7%F6%FB%FD%B0%A8%B0%D3%E7%F6%FB%FD%B0%BE%B0%FF%E1%F5%D7%FC%F6%D5%F3%FF%F7%C1%F1%FD%E0%F7%B0%A8%B0%DB%FC%FB%F1%FB%F3%B2%F7%FE%B2%F8%E7%F7%F5%FD%BC%BC%BC%B0%EF%EF
01234
Su navegador no es compatible con esta herramienta.

Practica con Floyd-Warshall

El pueblo de Carmen es muy pequeño y el grafo dirigido que describe las distancias de las calles que tiene que recorrer el cartero o la cartera cuando va en vehículo de motor es el siguiente:

Grafo Dirigido
Pilar Sabariego. Grafo Dirigido (CC BY-SA)

1

Carmen decide aplicar el algoritmo de Floyd-Warshall para calcular los caminos más cortos entre cualesquiera dos nodos. ¿Es correcto el paso correspondiente el nodo B?

Vértices A B C D E
A 0 1 2 3 3
B ∞ 0 ∞ 2 2
C 2 3 0 5 5
D ∞ ∞ ∞ 0 1
E ∞ 2 4 4 0
Vértices A B C D E
A A B C B B
B A B C D E
C A A C B B
D A B C D E
E A B C B E

2

Continúa aplicando el algoritmo y obtiene las siguientes matrices en el paso correspondiente al nodo D. ¿Ha realizado bien los pasos correspondientes a los nodos C y D?

Vértices A B C D E
A 0 1 2 3 3
B ∞ 0 ∞ 2 2
C 2 3 0 5 5
D ∞ ∞ ∞ 0 1
E 6 7 4 4 0
Vértices A B C D E
A A B C B B
B A B C D E
C A A C B B
D A B C D E
E C C C B E

3

Un par de días más tarde vuelve a aplicar el algoritmo y Carmen obtiene las siguientes matrices solución. ¿Son correctos sus cálculos? ¿Ha aplicado bien el algoritmo?
Vértices A B C D E
A 0 1 2 3 3
B 8 0 6 2 2
C 2 3 0 5 4
D 7 3 5 0 1
E 6 2 4 4 0
Vértices A B C D E
A A B C B B
B E B E D E
C A A C B E
D E E E D E
E C B C B E

4

Carmen quiere saber si los caminos mínimos serían los mismos si todas las calles se pudieran recorrer en los dos sentidos. Es decir, si el grafo fuera no dirigido:
Grafo No Dirigido
Pilar Sabariego. Grafo No Dirigido (CC BY-SA)

Tras volver a aplicar el algoritmo de Floyd-Warshall en el grafo no dirigido obtiene las siguientes matrices finales. Carmen cree que se ha equivocado porque la matriz de los pesos le ha salido simétrica. ¿Está en lo cierto? Razona tu respuesta

Vértices A B C D E
A 0 1 2 3 3
B 1 0 3 2 2
C 2 3 0 5 4
D 3 2 5 0 1
E 3 2 4 1 0
Vértices A B C D E
A A B C B B
B A B A D E
C A A C B E
D B B B D E
E B B C D E

Biografías

Edsger Wybe Dijkstra

Edsger Wybe Dijkstra nació el 11 de mayo de 1930 en Rotterdam (Holanda). Su padre fue químico y su madre matemática. En un principio, Dijkstra quería estudiar derecho para poder representar a los Países Bajos en las Naciones Unidas, pero tras realizar los exámenes finales de secundaria en 1948 obtuvo tan buenos resultados en matemáticas, física, química y biología que, tanto sus padres como sus profesores, lo persuadieron para que realizara una carrera de ciencias. Finalmente estudió física y matemáticas en la Universidad de Leyden, terminando en 1951. En la misma universidad obtuvo un doctorado en física teórica en 1956. Posteriormente, en 1959, obtuvo otro doctorado en la Universidad de Amsterdam.

En 1952 comenzó a trabajar en el Centro Matemático de Amsterdam donde aprendió a programar, convirtiéndose en el primer programador de Holanda.

Entre 1962 y 1984 fue profesor de la Universidad Tecnológica de Eindhoven, trabajo que compaginó con el de investigador para Burroughs entre 1973 y 1984, año en el que aceptó la cátedra de Schlumberger de la Universidad de Texas en Austin. Allí estuvo trabajando hasta que se jubiló en 1999.

Dijkstra se casó con Maria Debets en 1957 y tuvieron tres hijos: Marcus, Femke y Rutger. Este último, como su padre, se dedicó a la computación.

Murió el 6 de agosto 2002, en Nuenen (Holanda), víctima de cáncer.

En 1972 recibió el Premio Turing de las Ciencia de la Computación que es otorgado anualmente por la Asociación para la Maquinaria Computacional (ACM) a quienes hayan contribuido de manera trascendental al campo de las ciencias de la computación.

Poco después de su muerte también recibió la distinción ACM PODC Influental Paper Award en computación distribuida por su trabajo en la autoestabilización en programas computacionales. Este premio fue renombrado como Premio Dijkstra el siguiente año en su honor.

Dijkstra es considerado uno de los mayores desarrolladores de software de su época y, aunque parezca imposible, evitó el uso de ordenadores en su trabajo durante décadas. Todos sus trabajos fueron realizados a mano y únicamente utilizó los ordenadores para enviar correos electrónicos y hacer búsquedas en Internet.

El algoritmo para encontrar el camino mínimo en un grafo fue publicado en 1959, a pesar de que Dijkstra lo obtuvo en 1956. Este retraso en su publicación se debió a que en aquella época un algoritmo no se consideraba un logro científico. En la actualidad, este algoritmo ha sido usado como base para protocolos de enrutamiento en Internet, sistemas de posicionamiento global o simplemente para calcular los itinerarios óptimos de rutas de viaje.

Bernard Roy

Bernard Roy es un matemático francés nacido el 15 de marzo de 1934 y fallecido el 28 de octubre de 2017. En 1974 fundó el Laboratorio de Análisis y Modelización de Sistemas de Apoyo a la Decisión. Entre 1985 y 1986 fue presidente de la Asociación Europea de Sociedades de Investigación Operativa y en 1992 recibió la EURO Gold Medal, que es la mayor distinción europea en investigación operativa. Además, en 2015, también fue galardonado con el EURO Distinguished Service Award, un premio que reconoce el servicio prestado al desarrollo de la investigación operativa en Europa. Fue profesor emérito de la Universidad de París-Dauphine.

Roy trabajó en teoría de grafos y en análisis de decisión multicriterio, siendo el creador de ELECTRE, una familia de métodos de análisis de decisión multicriterio desarrollada en Europa entre 1960 y 1970.

En 1959 describió el algoritmo de Floyd-Warshall, siendo un ejemplo de programación dinámica. El algoritmo que aplicamos actualmente es el que publicó Robert Floyd en 1962, a pesar de que Bernard Roy (1959) y Stephen Warshall (1962) ya lo había publicado antes. Es más, hay otra tercera publicación en 1962 debida a Peter Ingerman que también incluye el algoritmo tal y como lo aplicamos en la actualidad. Recibe el nombre de Floyd-Warshall, aunque no fueran los primeros en publicarlo, por las contribuciones que ambos informáticos realizaron al desarrollo de los grafos de computación.

Creado con eXeLearning (Ventana nueva)

Financiado por la Unión Europea — Ministerio de Educación y Formación Profesional (Gobierno de España) — Plan de Recuperación, Transformación y Resiliencia