FloydWarshall
Páginas: 3 (599 palabras)
Publicado: 6 de julio de 2014
Algoritmo de FloydWarshall
Informática - Hoja de Ejercicios 7
Objetivo
Dado un grafo ponderado, queremos obtener el
camino de distancia mínima entre dos vértices
cualesquiera.
0
1
0
53
1
3
0
2
6
7
4
4
8
2
3
4
1
2
3
4
Objetivo
Dado un grafo ponderado, queremos obtener el
camino de distancia mínima entre dos vértices
cualesquiera.
0
10
5
3
1
3
0
2
6
7
4
4
8
2
3
4
1
2
3
8
4
Objetivo
Dado un grafo ponderado, queremos obtener el
camino de distancia mínima entre dos vérticescualesquiera.
0
1
0
5
3
1
3
0
2
6
7
4
4
8
2
3
4
1
2
3
4
8
14
Objetivo
Dado un grafo ponderado, queremos obtener el
camino de distancia mínimaentre dos vértices
cualesquiera.
0
2
3
4
0
0
3
7
8
14
1
3
0
9
5
11
2
1
1
7
9
0
4
8
3
8
5
4
0
6
4
14
118
6
0
5
3
3
0
6
7
4
4
8
2
Representación de un grafo
Matriz de adyacencia, con los pesos de cada
arista. Si no hay arista entre dos vértices
determinados, seconsidera +∞
0
2
3
4
0
0
3
7
+∞
+∞
1
3
0
+∞
5
+∞
2
1
1
7
+∞
0
4
8
3
+∞
5
4
0
6
4
+∞
+∞
8
6
0
53
3
0
6
7
4
4
8
2
Representación de un grafo
Matriz de adyacencia, con los pesos de cada
arista. Si no hay arista entre dos vértices
determinados, se considera +∞
0
23
4
0
0
3
7
+∞
+∞
1
3
0
+∞
5
+∞
2
1
1
7
+∞
0
4
8
3
+∞
5
4
0
6
4
+∞
+∞
8
6
0
5
3
3
0
67
4
4
8
2
Simétrica, con ceros en la diagonal
Representación de un grafo
Sólo almacenamos los elementos por debajo de
la diagonal principal.
0
1
2
3
4
0
0
3...
Informática - Hoja de Ejercicios 7
Objetivo
Dado un grafo ponderado, queremos obtener el
camino de distancia mínima entre dos vértices
cualesquiera.
0
1
0
53
1
3
0
2
6
7
4
4
8
2
3
4
1
2
3
4
Objetivo
Dado un grafo ponderado, queremos obtener el
camino de distancia mínima entre dos vértices
cualesquiera.
0
10
5
3
1
3
0
2
6
7
4
4
8
2
3
4
1
2
3
8
4
Objetivo
Dado un grafo ponderado, queremos obtener el
camino de distancia mínima entre dos vérticescualesquiera.
0
1
0
5
3
1
3
0
2
6
7
4
4
8
2
3
4
1
2
3
4
8
14
Objetivo
Dado un grafo ponderado, queremos obtener el
camino de distancia mínimaentre dos vértices
cualesquiera.
0
2
3
4
0
0
3
7
8
14
1
3
0
9
5
11
2
1
1
7
9
0
4
8
3
8
5
4
0
6
4
14
118
6
0
5
3
3
0
6
7
4
4
8
2
Representación de un grafo
Matriz de adyacencia, con los pesos de cada
arista. Si no hay arista entre dos vértices
determinados, seconsidera +∞
0
2
3
4
0
0
3
7
+∞
+∞
1
3
0
+∞
5
+∞
2
1
1
7
+∞
0
4
8
3
+∞
5
4
0
6
4
+∞
+∞
8
6
0
53
3
0
6
7
4
4
8
2
Representación de un grafo
Matriz de adyacencia, con los pesos de cada
arista. Si no hay arista entre dos vértices
determinados, se considera +∞
0
23
4
0
0
3
7
+∞
+∞
1
3
0
+∞
5
+∞
2
1
1
7
+∞
0
4
8
3
+∞
5
4
0
6
4
+∞
+∞
8
6
0
5
3
3
0
67
4
4
8
2
Simétrica, con ceros en la diagonal
Representación de un grafo
Sólo almacenamos los elementos por debajo de
la diagonal principal.
0
1
2
3
4
0
0
3...
Leer documento completo
Regístrate para leer el documento completo.