tag:blogger.com,1999:blog-11031493211500224572024-03-13T22:09:42.190-07:00Algoritmo de FloydSonnier Josehttp://www.blogger.com/profile/10471773210803344377noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-1103149321150022457.post-14933413054301070892013-02-15T07:05:00.002-08:002013-02-15T07:05:30.229-08:00Teorias explicitas y ejemplos<h3 style="padding-left: 60px;">
<span style="color: red;">Algoritmo DE FLOYD</span></h3>
<div style="text-align: justify;">
El algoritmo de Floyd es más general que
el de Dijkstra, ya que determina la ruta más corta entre dos nodos
cualquiera de la red.</div>
<ul style="text-align: justify;">
<li>El algoritmo representa una red de <em>n</em> nodos como una matriz cuadrada de orden <em>n</em>, la llamaremos matriz <em>C</em>. De esta forma, el valor <em>Cij</em> representa el coste de ir desde el nodo <em>i </em>al nodo <em>j</em>, inicialmente en caso de no existir un arco entre ambos, el valor <em>Cij</em> será infinito.</li>
<li>Definiremos otra matriz <em>D</em>, también cuadrada de orden <em>n</em>, cuyos elementos van a ser los nodos predecesores en el camino hacia el nodo origen, es decir, el valor <em>Dij</em> representará el nodo predecesor a <em>j</em> en el camino mínimo desde <em>i</em> hasta <em>j</em>. Inicialmente se comienza con caminos de longitud <em>1</em>, por lo que <em>Dij = i</em>.</li>
<li>Las diagonales de ambas matrices representan el coste y el nodo
predecesor para ir de un nodo a si mismo, por lo que no sirven para
nada, estarán bloqueadas.</li>
</ul>
<div style="text-align: justify;">
Los pasos a dar en la aplicación del algoritmo de Floyd son los siguientes: </div>
<ul style="text-align: justify;">
<li>Formar las matrices iniciales <em>C</em> y <em>D</em>.</li>
<li>Se toma <em>k=1</em>.</li>
<li>Se selecciona la fila y la columna <em>k</em> de la matriz <em>C</em> y entonces, para <em>i</em> y <em>j</em>, con <em>i≠k</em>, <em>j≠k</em> e <em>i≠j</em>, hacemos:</li>
</ul>
<div style="text-align: justify;">
Si <em>(Cik + Ckj) < Cij → Dij = Dkj</em> y <em>Cij = Cik + Ckj</em></div>
<div style="text-align: justify;">
En caso contrario, dejamos las matrices como están. </div>
<ul style="text-align: justify;">
<li>Si <em>k ≤ n</em>, aumentamos <em>k</em> en una unidad y repetimos el paso anterior, en caso contrario paramos las iteraciones.</li>
<li>La matriz final <em>C</em> contiene los costes óptimos para ir de un vértice a otro, mientras que la matriz <em>D</em>
contiene los penúltimos vértices de los caminos óptimos que unen dos
vértices, lo cual permite reconstruir cualquier camino óptimo para ir de
un vértice a otro.</li>
</ul>
<div style="text-align: justify;">
<strong><span style="color: blue;"><span style="text-decoration: underline;">Ejemplo:</span></span></strong> Aplicar el algoritmo de Floyd sobre el siguiente grafo para obtener las rutas más cortas entre cada dos nodos. El arco <em>(3, 5)</em> es direccional, de manera que no está permitido ningún tráfico del nodo <em>5</em> al nodo <em>3</em> . Todos los demás arcos permiten el tráfico en ambas direcciones.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: center;">
<a href="http://karenbandala.files.wordpress.com/2010/04/diagrama3.png"><img alt="" class="size-full wp-image-218 aligncenter" height="191" src="http://karenbandala.files.wordpress.com/2010/04/diagrama3.png?w=355&h=191" title="diagrama3" width="355" /></a></div>
<br />
<div style="text-align: center;">
Inicializamos las matrices :<a href="http://karenbandala.files.wordpress.com/2010/04/matriz3.png"><img alt="" class="size-full wp-image-220 aligncenter" height="209" src="http://karenbandala.files.wordpress.com/2010/04/matriz3.png?w=355&h=209" title="matriz3" width="355" /></a></div>
<br />
<div style="text-align: center;">
Tomamos <em>k=1</em>:<a href="http://karenbandala.files.wordpress.com/2010/04/matriz4.png"><img alt="" class="size-full wp-image-221 aligncenter" height="208" src="http://karenbandala.files.wordpress.com/2010/04/matriz4.png?w=354&h=208" title="matriz4" width="354" /></a></div>
<br />
Tomamos <em>i=2 (i ≠k)</em>:<br />
<ul>
<li><em>j=3 (j≠k, j≠i)</em>: <em>C[2,1]+C[1,3] = 3+10 = 13 < C[2,3] = ∞</em>, por tanto hacemos:</li>
</ul>
<em><strong>C[2,3] = 13</strong></em> y <em><strong>D[2,3] = 1</strong></em>.<br />
<ul>
<li><em>j=4 (j≠k, j≠i): C[2,1]+C[1,4] = 3+∞ = ∞</em>, no hay que cambiar nada, no podemos llegar de <em>2</em> a <em>4</em> a través de <em>1</em>.</li>
<li><em>j=5 (j≠k, j≠i): C[2,1]+C[1,5] = 3+∞ = ∞</em>, no hay que cambiar nada, no podemos llegar de <em>2</em> a <em>5</em> a través de <em>1</em>.</li>
<li>Tomamos <em>i=3 (i ≠k)</em>:
<ul>
<li><em>j=2 (j≠k, j≠i)</em>: <em>C[3,1]+C[1,2] = 10+3 = 13 < C[3,2] = ∞</em>, por tanto hacemos:</li>
</ul>
</li>
</ul>
<em><strong>C[3,2] = 13</strong></em> y <em><strong>D[3,2] = 1</strong></em>.<br />
<ul>
<li><em>j=4 (j≠k, j≠i)</em>: <em>C[3,1]+C[1,4] = 10+∞ = ∞</em>, no hay que cambiar nada, no podemos llegar de <em>3</em> a <em>4</em> a través de <em>1</em>.</li>
<li><em>j=5 (j≠k, j≠i)</em>: <em>C[3,1]+C[1,5] = 10+∞ = ∞</em>, no hay que cambiar nada, no podemos llegar de <em>3</em> a <em>5</em> a través de <em>1</em>.</li>
<li>Tomamos <em>i=4 (i ≠k)</em>:
<ul>
<li><em>j=2 (j≠k, j≠i)</em>: <em>C[4,1]+C[1,2] = ∞+3 = ∞</em>, no hay que cambiar nada, no podemos llegar de <em>4</em> a <em>2</em> a través de <em>1</em>.</li>
<li><em>j=3 (j≠k, j≠i)</em>: <em>C[4,1]+C[1,3] = ∞+10 = ∞</em>, no hay que cambiar nada, no podemos llegar de <em>4</em> a <em>3</em> a través de <em>1</em>.</li>
<li><em>j=5 (j≠k, j≠i)</em>: <em>C[4,1]+C[1,5] = ∞+∞ = ∞</em>, no hay que cambiar nada, no podemos llegar de <em>4</em> a <em>5</em> a través de <em>1</em>.</li>
</ul>
</li>
</ul>
Tomamos <em>i=5 (i ≠k)</em>, en este caso ocurre como en el paso anterior, como <em>C[5,1]=∞</em>, entonces no habrá ningún cambio, no puede haber ningún camino desde <em>5</em> a través de <em>1</em>.<br />
<div style="text-align: center;">
Tomamos <em>k=2</em>:<img alt="" class="size-full wp-image-223 aligncenter" height="208" src="http://karenbandala.files.wordpress.com/2010/04/matriz5.png?w=354&h=208" title="matriz5" width="354" /></div>
Tomamos <em>i=1</em>:<br />
<ul>
<li><em>j=3</em>: <em>C[1,2]+C[2,3] = 3+13 = 16 > C[1,3] = 10 </em>, por tanto no hay que cambiar nada, el camino es mayor que el existente.</li>
<li><em>j=4</em>:<em> C[1,2]+C[2,4] = 3+5 = 8 < C[1,4] = ∞</em>, por tanto hacemos:</li>
</ul>
<em><strong>C[1,4] = 8 </strong></em>y <em><strong>D[1,4] = 2 </strong></em>.<br />
<ul>
<li><em>j=5</em>:<em> C[1,2]+C[2,5] = 3+∞ = ∞</em>, no hay que cambiar nada.</li>
<li>Tomamos <em>i=3</em>:
<ul>
<li><em>j=1</em>: <em>C[3,2]+C[2,1] = 13+3 = 16 > C[3,1] = 10</em>, no hay que cambiar nada.</li>
<li><em>j=4</em>: <em>C[3,2]+C[2,4] = 13+5 = 18 > C[3,4] = 6</em>, no hay que cambiar nada.</li>
<li><em>j=5</em>: <em>C[3,2]+C[2,5] = 13+∞ = ∞</em>, no hay que cambiar nada.</li>
</ul>
</li>
<li>Tomamos <em>i=4</em>:
<ul>
<li><em>j=1</em>: <em>C[4,2]+C[2,1] = 5+3 = 8 < C[4,1] = ∞</em>, por tanto hacemos:</li>
</ul>
</li>
</ul>
<em><strong>C[4,1] = 8 </strong></em>y <em><strong>D[4,1] = 2</strong></em>.<br />
<ul>
<li><em>j=3</em>: <em>C[4,2]+C[2,3] = 5+13 = 18 > C[4,3] = 6</em>, no hay que cambiar nada.</li>
<li><em>j=5</em>: <em>C[4,2]+C[2,5] = 5+∞ = ∞</em>, no hay que cambiar nada.</li>
</ul>
Tomamos <em>i=5</em>, como <em>C[5,2]=∞</em>, entonces no habrá ningún cambio.<br />
<div style="text-align: center;">
Tomamos <em>k=3</em>:<a href="http://karenbandala.files.wordpress.com/2010/04/matriz6.png"><img alt="" class="size-full wp-image-225 aligncenter" height="208" src="http://karenbandala.files.wordpress.com/2010/04/matriz6.png?w=353&h=208" title="matriz6" width="353" /></a></div>
<br />
<ul>
<li>Tomamos <em>i=1</em>:
<ul>
<li><em>j=2</em>: <em>C[1,3]+C[3,2] = 10+13 = 23 > C[1,2] = 3</em>, no hay que cambiar nada.</li>
<li><em>j=4</em>:<em> C[1,3]+C[3,4] = 10+6 = 16 > C[1,4] = 8</em>, no hay que cambiar nada.</li>
<li><em>j=5</em>:<em> C[1,3]+C[3,5] = 10+15 = 25 < C[1,5] = ∞</em>, por tanto hacemos:</li>
</ul>
</li>
</ul>
<em><strong>C[1,5] = 25 </strong></em>y <em><strong>D[1,5] = 3 </strong></em>.<br />
<ul>
<li>Tomamos <em>i=2</em>:
<ul>
<li><em>j=1</em>: <em>C[2,3]+C[3,1] = 13+10 = 23 > C[2,1] = 3</em>, no hay que cambiar nada.</li>
<li><em>j=4</em>: <em>C[2,3]+C[3,4] = 13+6 = 19 > C[2,4] = 5</em>, no hay que cambiar nada.</li>
<li><em>j=5</em>: <em>C[2,3]+C[3,5] = 13+15 = 28 < C[2,5] = ∞</em>, por tanto hacemos:</li>
</ul>
</li>
</ul>
<em><strong>C[2,5] = 28</strong></em> y <em><strong>D[2,5] = 3</strong></em>.<br />
<ul>
<li>Tomamos <em>i=4</em>:
<ul>
<li><em>j=1</em>: <em>C[4,3]+C[3,1] = 6+10 = 16 > C[4,1] = 8</em>, no hay que cambiar nada.</li>
<li><em>j=2</em>: <em>C[4,3]+C[3,2] = 6+13 = 19 > C[4,2] = 5</em>, no hay que cambiar nada.</li>
<li><em>j=5</em>: <em>C[4,3]+C[3,5] = 6+15 = 21 > C[4,5] = 4</em>, no hay que cambiar nada.</li>
</ul>
</li>
</ul>
Tomamos <em>i=5</em>, como <em>C[5,3]=∞</em>, entonces no habrá ningún cambio.<br />
<div style="text-align: center;">
Tomamos <em>k=4</em>:<img alt="" class="size-full wp-image-226 aligncenter" height="207" src="http://karenbandala.files.wordpress.com/2010/04/matriz7.png?w=356&h=207" title="matriz7" width="356" /></div>
<ul>
<li>Tomamos <em>i=1</em>:
<ul>
<li><em>j=2</em>: <em>C[1,4]+C[4,2] = 8+5 = 13 > C[1,2] = 3</em>, no hay que cambiar nada.</li>
<li><em>j=3</em>:<em> C[1,4]+C[4,3] = 8+6 = 14 > C[1,3] = 10</em>, no hay que cambiar nada.</li>
<li><em>j=5</em>:<em> C[1,4]+C[4,5] = 8+4 = 12 < C[1,5] = 25</em>, por tanto hacemos:</li>
</ul>
</li>
</ul>
<em><strong>C[1,5] = 12 </strong></em>y <em><strong>D[1,5] = 4</strong></em>.<br />
<ul>
<li>Tomamos <em>i=2</em>:
<ul>
<li><em>j=1</em>: <em>C[2,4]+C[4,1] = 5+8 = 13 > C[2,1] = 3</em>, no hay que cambiar nada.</li>
<li><em>j=3</em>: <em>C[2,4]+C[4,3] = 5+6 = 11 < C[2,3] = 13</em>, por tanto hacemos:</li>
</ul>
</li>
</ul>
<em><strong>C[2,3] = 11 </strong></em>y <em><strong>D[2,3] = 4</strong></em>.<br />
<ul>
<li><em>j=5</em>: <em>C[2,4]+C[4,5] = 5+4 = 9 < C[2,5] = 28</em>, por tanto hacemos:</li>
</ul>
<em><strong>C[2,5] = 9 </strong></em>y <em><strong>D[2,5] = 4</strong></em>.<br />
<ul>
<li>Tomamos <em>i=3</em>:
<ul>
<li><em>j=1</em>: <em>C[3,4]+C[4,1] = 6+8 = 14 > C[3,1] = 10</em>, no hay que cambiar nada.</li>
<li><em>j=2</em>: <em>C[3,4]+C[4,2] = 6+5 = 11 < C[3,2] = 13</em>, por tanto hacemos:</li>
</ul>
</li>
</ul>
<em><strong>C[3,2] = 11 </strong></em>y <em><strong>D[3,2] = 4</strong></em>.<br />
<ul>
<li><em>j=5</em>: <em>C[3,4]+C[4,5] = 6+4 = 10 < C[3,5] = 15</em>, por tanto hacemos:</li>
</ul>
<em><strong>C[3,5] = 10 </strong></em>y <em><strong>D[3,5] = 4</strong></em>.<br />
<ul>
<li>Tomamos <em>i=5</em>:
<ul>
<li><em>j=1</em>: <em>C[5,4]+C[4,1] = 4+8 = 12 < C[5,1] = ∞</em>, por tanto hacemos:</li>
</ul>
</li>
</ul>
<em><strong>C[5,1] = 12</strong></em> y <em><strong>D[5,1] = 2 </strong></em>.<br />
<ul>
<li><em>j=2</em>: <em>C[5,4]+C[4,2] = 4+5 = 9 < C[5,2] = ∞</em>, por tanto hacemos:</li>
</ul>
<em><strong>C[5,2] = 9 </strong></em>y <em><strong>D[5,2] = 4</strong></em>.<br />
<ul>
<li><em>j=3</em>: <em>C[5,4]+C[4,3] = 4+6 = 10 < C[5,3] = ∞</em>, por tanto hacemos:</li>
</ul>
<em><strong>C[5,3] = 10</strong></em> y <em><strong>D[5,3] = 4</strong></em>.<br />
<div style="text-align: center;">
Tomamos <em>k=5</em>:<a href="http://karenbandala.files.wordpress.com/2010/04/matriz8.png"><img alt="" class="size-full wp-image-227 aligncenter" height="206" src="http://karenbandala.files.wordpress.com/2010/04/matriz8.png?w=354&h=206" title="matriz8" width="354" /></a></div>
<br />
<table border="0" cellpadding="0" style="width: 80%px;">
<tbody>
<tr>
<td>
<ul>
<li>Tomamos <em>i=1</em>:
<ul>
<li><em>j=2</em>: <em>C[1,5]+C[5,2] = 12+9 = 21 > C[1,2] = 3</em>, no hay que cambiar nada.</li>
<li><em>j=3</em>:<em> C[1,5]+C[5,3] = 12+10 = 22 > C[1,3] = 10</em>, no hay que cambiar nada.</li>
<li><em>j=4</em>:<em> C[1,5]+C[5,4] = 12+4 = 16 > C[1,4] = 8</em>, no hay que cambiar nada.</li>
</ul>
</li>
<li>Tomamos <em>i=2</em>:
<ul>
<li><em>j=1</em>: <em>C[2,5]+C[5,1] = 9+12 = 21 > C[2,1] = 3</em>, no hay que cambiar nada.</li>
<li><em>j=3</em>: <em>C[2,5]+C[5,3] = 9+10 = 19 > C[2,3] = 11</em>, no hay que cambiar nada.</li>
<li><em>j=4</em>: <em>C[2,5]+C[5,4] = 9+4 = 13 > C[2,4] = 5</em>, no hay que cambiar nada.</li>
</ul>
</li>
<li>Tomamos <em>i=3</em>:
<ul>
<li><em>j=1</em>: <em>C[3,5]+C[5,1] = 10+12 = 22 > C[3,1] = 10</em>, no hay que cambiar nada.</li>
<li><em>j=2</em>: <em>C[3,5]+C[5,2] = 10+9 = 19 > C[3,2] = 11</em>, no hay que cambiar nada.</li>
<li><em>j=4</em>: <em>C[3,5]+C[5,4] = 10+4 = 14 > C[3,4] = 6</em>, no hay que cambiar nada.</li>
</ul>
</li>
<li>Tomamos <em>i=4</em>:
<ul>
<li><em>j=1</em>: <em>C[4,5]+C[5,1] = 4+12 = 16 > C[4,1] = 8 </em>, no hay que cambiar nada.</li>
<li><em>j=2</em>: <em>C[4,5]+C[5,2] = 4+9 = 13 > C[4,2] = 5 </em>, no hay que cambiar nada.</li>
<li><em>j=3</em>: <em>C[4,5]+C[5,3] = 4+10 = 14 > C[4,3] = 6</em>, no hay que cambiar nada.</li>
</ul>
</li>
</ul>
</td>
</tr>
</tbody>
</table>
<div style="text-align: center;">
FIN del proceso, las matrices quedan como sigue:<a href="http://karenbandala.files.wordpress.com/2010/04/matriz9.png"><img alt="" class="size-full wp-image-229 aligncenter" height="206" src="http://karenbandala.files.wordpress.com/2010/04/matriz9.png?w=353&h=206" title="matriz9" width="353" /></a></div>
<ul>
<li>Las matrices finales <em>C </em>y <em>D</em> contienen toda la
información necesaria para determinar la ruta más corta entre dos nodos
cualquiera de la red. Por ejemplo, la distancia más corta del nodo <em>1</em> al nodo <em>5</em> es <em>C[1,5] = 12</em>.</li>
<li>Para determinar la ruta asociada del camino mínimo entre el nodo <em>1</em> y el nodo <em>5 </em>haremos lo siguiente:
<ul>
<li>Consultamos <em>D[1,5]=4</em>, por tanto el nodo predecesor al <em>5</em> es el <em>4</em>, es decir, <em>4</em> → <em>5</em>.</li>
<li>Consultamos <em>D[1,4]=2</em>, por tanto el nodo predecesor al <em>4</em> es el <em>2</em>, es decir, <em>2 </em>→<em> 4</em> → <em>5</em>.</li>
</ul>
</li>
</ul>
Consultamos <em>D[1,2]=1</em>, por tanto el nodo predecesor al <em>2</em> es el <em>1</em>, es decir, <em>1 </em>→<em> 2 </em>→<em> 4</em> → <em>5</em>, y así ya tenemos la ruta completa.<span id="_marker"> </span>Sonnier Josehttp://www.blogger.com/profile/10471773210803344377noreply@blogger.com1tag:blogger.com,1999:blog-1103149321150022457.post-36848430281603854152013-02-15T06:59:00.000-08:002013-02-15T06:59:09.028-08:00Bases Teoricas<h1 class="firstHeading" id="firstHeading" lang="es" style="text-align: center;">
<span dir="auto">Algoritmo de Floyd:</span></h1>
<div class="mw-jump" id="jump-to-nav" style="text-align: justify;">
<br />
<a href="http://es.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshall#p-search"></a>
</div>
<div style="text-align: justify;">
En <a href="http://es.wikipedia.org/wiki/Inform%C3%A1tica" title="Informática">informática</a>, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un <a href="http://es.wikipedia.org/wiki/Algoritmo" title="Algoritmo">algoritmo</a> de análisis sobre <a href="http://es.wikipedia.org/wiki/Grafo" title="Grafo">grafos</a> para encontrar el <a class="mw-redirect" href="http://es.wikipedia.org/wiki/Problema_de_los_caminos_m%C3%A1s_cortos" title="Problema de los caminos más cortos">camino mínimo</a>
en grafos dirigidos ponderados. El algoritmo encuentra el camino entre
todos los pares de vértices en una única ejecución. El algoritmo de
Floyd-Warshall es un ejemplo de <a class="mw-redirect" href="http://es.wikipedia.org/wiki/Programaci%C3%B3n_din%C3%A1mica_%28computaci%C3%B3n%29" title="Programación dinámica (computación)">programación dinámica</a>.</div>
<div style="text-align: justify;">
<br /></div>
<h2 style="text-align: center;">
<span class="mw-headline" id="Aplicaciones_y_generalizaciones">Aplicaciones: </span></h2>
El algoritmo de Floyd-Warshall puede ser utilizado para resolver los siguientes problemas, entre otros:<br />
<ul>
<li>Camino mínimo en <a href="http://es.wikipedia.org/wiki/Grafo_dirigido#Grafo_dirigido" title="Grafo dirigido">grafos dirigidos</a> (algoritmo de Floyd).</li>
<li>Cierre transitivo en grafos dirigidos (algoritmo de Warshall). Es la formulación original del algoritmo de Warshall. El <a href="http://es.wikipedia.org/wiki/Grafo" title="Grafo">grafo</a>
es un grafo no ponderado y representado por una matriz booleana de
adyacencia. Entonces la operación de adición es reemplazada por la <a href="http://es.wikipedia.org/wiki/Conjunci%C3%B3n_l%C3%B3gica" title="Conjunción lógica">conjunción lógica(AND)</a> y la operación menor por la <a href="http://es.wikipedia.org/wiki/Disyunci%C3%B3n_l%C3%B3gica" title="Disyunción lógica">disyunción lógica (OR)</a>.</li>
<li>Encontrar una <a href="http://es.wikipedia.org/wiki/Expresi%C3%B3n_regular" title="Expresión regular">expresión regular</a> dada por un <a href="http://es.wikipedia.org/wiki/Lenguaje_regular" title="Lenguaje regular">lenguaje regular</a> aceptado por un <a href="http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito" title="Autómata finito">autómata finito</a> (algoritmo de Kleene).</li>
<li><a href="http://es.wikipedia.org/wiki/Matriz_invertible" title="Matriz invertible">Inversión</a> de matrices de <a href="http://es.wikipedia.org/wiki/N%C3%BAmero_real" title="Número real">números reales</a> (<a href="http://es.wikipedia.org/wiki/Eliminaci%C3%B3n_de_Gauss-Jordan" title="Eliminación de Gauss-Jordan">algoritmo de Gauss-Jordan</a>).</li>
<li>Ruta optima. En esta aplicación es interesante encontrar el camino
del flujo máximo entre 2 vértices. Esto significa que en lugar de tomar
los mínimos con el pseudocodigo anterior, se coge el máximo. Los pesos
de las aristas representan las limitaciones del flujo. Los pesos de los
caminos representan cuellos de botella; por ello, la operación de
adición anterior es reemplazada por la operación mínimo.</li>
<li>Comprobar si un <a href="http://es.wikipedia.org/wiki/Grafo#Grafo_no_dirigido" title="Grafo">grafo no dirigido</a> es <a href="http://es.wikipedia.org/wiki/Grafo_bipartito" title="Grafo bipartito">bipartito</a>.</li>
</ul>
<br />
<h2>
<span class="mw-headline" id="Ejemplo">Ejemplo:</span></h2>
Hallar el camino mínimo desde el vértice 3 hasta 4 en el <a href="http://es.wikipedia.org/wiki/Grafo" title="Grafo">grafo</a> con la siguiente matriz de distancias:<br />
<dl><dd><img alt="D = \begin{bmatrix}
0 & 3 & 5 & 1 & \infty & \infty\\
3 & 0 & \infty & \infty & 9 & \infty\\
5 & \infty & 0 & 7 & 7 & 1\\
1 & \infty & 7 & 0 & \infty & 4\\
\infty & 9 & 7 & \infty & 0 & \infty\\
\infty & \infty & 1 & 4 & \infty & 0\end{bmatrix}" class="tex" src="http://upload.wikimedia.org/math/8/d/4/8d4a7da4332bfb32f8f8d6b48e7c2100.png" /></dd></dl>
<br />
Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteración fijamos un vértice intermedio.<br />
<br />
<b>1ª Iteración:</b> nodo intermedio = 1<br />
La matriz es simétrica, por lo que solamente hará falta calcular el triángulo superior de las distancias.<br />
d<sub>23</sub> = min(d<sub>23</sub>, d<sub>21</sub> + d<sub>13</sub>) = 8<br />
d<sub>24</sub> = min(d<sub>24</sub>, d<sub>21</sub> + d<sub>14</sub>) = 4<br />
d<sub>25</sub> = min(d<sub>25</sub>, d<sub>21</sub> + d<sub>15</sub>) = 9<br />
d<sub>26</sub> = min(d<sub>26</sub>, d<sub>21</sub> + d<sub>16</sub>) = <img alt="\infty" class="tex" src="http://upload.wikimedia.org/math/d/2/4/d245777abca64ece2d5d7ca0d19fddb6.png" /><br />
d<sub>32</sub> = min(d<sub>32</sub>, d<sub>31</sub> + d<sub>12</sub>) = 8<br />
d<sub>34</sub> = min(d<sub>34</sub>, d<sub>31</sub> + d<sub>14</sub>) = 6<br />
d<sub>35</sub> = min(d<sub>35</sub>, d<sub>31</sub> + d<sub>15</sub>) = 7<br />
d<sub>36</sub> = min(d<sub>36</sub>, d<sub>31</sub> + d<sub>16</sub>) = 1<br />
d<sub>45</sub> = min(d<sub>45</sub>, d<sub>41</sub> + d<sub>15</sub>) = <img alt="\infty" class="tex" src="http://upload.wikimedia.org/math/d/2/4/d245777abca64ece2d5d7ca0d19fddb6.png" /><br />
d<sub>46</sub> = min(d<sub>46</sub>, d<sub>41</sub> + d<sub>16</sub>) = 4<br />
d<sub>56</sub> = min(d<sub>56</sub>, d<sub>51</sub> + d<sub>16</sub>) = <img alt="\infty" class="tex" src="http://upload.wikimedia.org/math/d/2/4/d245777abca64ece2d5d7ca0d19fddb6.png" /><br />
La matriz de distancia después de esta iteración es:<br />
<dl><dd><img alt="\mathcal{W}_1 = \begin{bmatrix}
0 & 3 & 5 & 1 & \infty & \infty\\
3 & 0 & 8 & 4 & 9 & \infty\\
5 & 8 & 0 & 6 & 7 & 1\\
1 & 4 & 6 & 0 & \infty & 4\\
\infty & 9 & 7 & \infty & 0 & \infty\\
\infty & \infty & 1 & 4 & \infty & 0\end{bmatrix}" class="tex" src="http://upload.wikimedia.org/math/6/a/7/6a79d7fecddda7dd483b4460c3f7a28a.png" /></dd></dl>
<b>2ª Iteración:</b> nodo intermedio = 2<br />
d<sub>13</sub> = min(d<sub>13</sub>, d<sub>12</sub> + d<sub>23</sub>) = 5<br />
d<sub>14</sub> = min(d<sub>14</sub>, d<sub>12</sub> + d<sub>24</sub>) = 1<br />
d<sub>15</sub> = min(d<sub>15</sub>, d<sub>12</sub> + d<sub>25</sub>) = 12<br />
d<sub>16</sub> = min(d<sub>16</sub>, d<sub>12</sub> + d<sub>26</sub>) = <img alt="\infty" class="tex" src="http://upload.wikimedia.org/math/d/2/4/d245777abca64ece2d5d7ca0d19fddb6.png" /><br />
d<sub>34</sub> = min(d<sub>34</sub>, d<sub>32</sub> + d<sub>24</sub>) = 6<br />
d<sub>35</sub> = min(d<sub>35</sub>, d<sub>32</sub> + d<sub>25</sub>) = 7<br />
d<sub>36</sub> = min(d<sub>36</sub>, d<sub>32</sub> + d<sub>26</sub>) = 1<br />
d<sub>45</sub> = min(d<sub>45</sub>, d<sub>42</sub> + d<sub>25</sub>) = 13<br />
d<sub>46</sub> = min(d<sub>46</sub>, d<sub>42</sub> + d<sub>26</sub>) = 4<br />
d<sub>56</sub> = min(d<sub>56</sub>, d<sub>52</sub> + d<sub>26</sub>) = <img alt="\infty" class="tex" src="http://upload.wikimedia.org/math/d/2/4/d245777abca64ece2d5d7ca0d19fddb6.png" /><br />
La matriz de distancia después de esta iteración es:<br />
<dl><dd><img alt="\mathcal{W}_2 = \begin{bmatrix}
0 & 3 & 5 & 1 & 12 & \infty\\
3 & 0 & 8 & 4 & 9 & \infty\\
5 & 8 & 0 & 6 & 7 & 1\\
1 & 4 & 6 & 0 & 13 & 4\\
12 & 9 & 7 & 13 & 0 & \infty\\
\infty & \infty & 1 & 4 & \infty & 0\end{bmatrix}" class="tex" src="http://upload.wikimedia.org/math/5/2/1/5212ad5e0da3266482e877e9fec3ce82.png" /></dd></dl>
<b>3ª Iteración:</b> nodo intermedio = 3<br />
d<sub>12</sub> = min(d<sub>12</sub>, d<sub>13</sub> + d<sub>32</sub>) = 3<br />
d<sub>14</sub> = min(d<sub>14</sub>, d<sub>13</sub> + d<sub>34</sub>) = 1<br />
d<sub>15</sub> = min(d<sub>15</sub>, d<sub>13</sub> + d<sub>35</sub>) = 12<br />
d<sub>16</sub> = min(d<sub>16</sub>, d<sub>13</sub> + d<sub>36</sub>) = 6<br />
d<sub>24</sub> = min(d<sub>24</sub>, d<sub>23</sub> + d<sub>34</sub>) = 4<br />
d<sub>25</sub> = min(d<sub>25</sub>, d<sub>23</sub> + d<sub>35</sub>) = 9<br />
d<sub>26</sub> = min(d<sub>26</sub>, d<sub>23</sub> + d<sub>36</sub>) = 9<br />
d<sub>45</sub> = min(d<sub>45</sub>, d<sub>43</sub> + d<sub>35</sub>) = 13<br />
d<sub>46</sub> = min(d<sub>46</sub>, d<sub>43</sub> + d<sub>36</sub>) = 4<br />
d<sub>56</sub> = min(d<sub>56</sub>, d<sub>53</sub> + d<sub>36</sub>) = 8<br />
La matriz de distancia después de esta iteración es:<br />
<dl><dd><img alt="\mathcal{W}_3 = \begin{bmatrix}
0 & 3 & 5 & 1 & 12 & 6\\
3 & 0 & 8 & 4 & 9 & 9\\
5 & 8 & 0 & 6 & 7 & 1\\
1 & 4 & 6 & 0 & 13 & 4\\
12 & 9 & 7 & 13 & 0 & 8\\
6 & 9 & 1 & 4 & 8 & 0\end{bmatrix}" class="tex" src="http://upload.wikimedia.org/math/9/a/7/9a7f5354307d42bd6e23f63ba51b8cf6.png" /></dd></dl>
<b>4ª Iteración:</b> nodo intermedio = 4<br />
d<sub>12</sub> = min(d<sub>12</sub>, d<sub>14</sub> + d<sub>42</sub>) = 3<br />
d<sub>13</sub> = min(d<sub>13</sub>, d<sub>14</sub> + d<sub>43</sub>) = 5<br />
d<sub>15</sub> = min(d<sub>15</sub>, d<sub>14</sub> + d<sub>45</sub>) = 12<br />
d<sub>16</sub> = min(d<sub>16</sub>, d<sub>14</sub> + d<sub>46</sub>) = 5<br />
d<sub>23</sub> = min(d<sub>23</sub>, d<sub>24</sub> + d<sub>43</sub>) = 8<br />
d<sub>25</sub> = min(d<sub>25</sub>, d<sub>24</sub> + d<sub>45</sub>) = 9<br />
d<sub>26</sub> = min(d<sub>26</sub>, d<sub>24</sub> + d<sub>46</sub>) = 8<br />
d<sub>35</sub> = min(d<sub>35</sub>, d<sub>34</sub> + d<sub>45</sub>) = 7<br />
d<sub>36</sub> = min(d<sub>36</sub>, d<sub>34</sub> + d<sub>46</sub>) = 1<br />
d<sub>56</sub> = min(d<sub>56</sub>, d<sub>54</sub> + d<sub>46</sub>) = 8<br />
La matriz de distancia después de esta iteración es:<br />
<dl><dd><img alt="\mathcal{W}_4 = \begin{bmatrix}
0 & 3 & 5 & 1 & 12 & 5\\
3 & 0 & 8 & 4 & 9 & 8\\
5 & 8 & 0 & 6 & 7 & 1\\
1 & 4 & 6 & 0 & 13 & 4\\
12 & 9 & 7 & 13 & 0 & 8\\
5 & 8 & 1 & 4 & 8 & 0\end{bmatrix}" class="tex" src="http://upload.wikimedia.org/math/0/e/9/0e921b8797bf37498cf8465e0fa544bc.png" /></dd></dl>
<b>5ª Iteración:</b> nodo intermedio = 5<br />
d<sub>12</sub> = min(d<sub>12</sub>, d<sub>15</sub> + d<sub>52</sub>) = 3<br />
d<sub>13</sub> = min(d<sub>13</sub>, d<sub>15</sub> + d<sub>53</sub>) = 5<br />
d<sub>14</sub> = min(d<sub>14</sub>, d<sub>15</sub> + d<sub>54</sub>) = 1<br />
d<sub>16</sub> = min(d<sub>16</sub>, d<sub>15</sub> + d<sub>56</sub>) = 5<br />
d<sub>23</sub> = min(d<sub>23</sub>, d<sub>25</sub> + d<sub>53</sub>) = 8<br />
d<sub>24</sub> = min(d<sub>24</sub>, d<sub>25</sub> + d<sub>54</sub>) = 4<br />
d<sub>26</sub> = min(d<sub>26</sub>, d<sub>25</sub> + d<sub>56</sub>) = 8<br />
d<sub>34</sub> = min(d<sub>34</sub>, d<sub>35</sub> + d<sub>54</sub>) = 6<br />
d<sub>36</sub> = min(d<sub>36</sub>, d<sub>35</sub> + d<sub>56</sub>) = 1<br />
d<sub>46</sub> = min(d<sub>46</sub>, d<sub>45</sub> + d<sub>56</sub>) = 4<br />
La matriz de distancia después de esta iteración es:<br />
<dl><dd><img alt="\mathcal{W}_5 = \mathcal{W}_4 = \begin{bmatrix}
0 & 3 & 5 & 1 & 12 & 5\\
3 & 0 & 8 & 4 & 9 & 8\\
5 & 8 & 0 & 6 & 7 & 1\\
1 & 4 & 6 & 0 & 13 & 4\\
12 & 9 & 7 & 13 & 0 & 8\\
5 & 8 & 1 & 4 & 8 & 0\end{bmatrix}" class="tex" src="http://upload.wikimedia.org/math/e/6/6/e668974df9f3860685b2352d6bc467c5.png" /></dd></dl>
<b>6ª Iteración:</b> nodo intermedio = 6<br />
d<sub>12</sub> = min(d<sub>12</sub>, d<sub>16</sub> + d<sub>62</sub>) = 3<br />
d<sub>13</sub> = min(d<sub>13</sub>, d<sub>16</sub> + d<sub>63</sub>) = 5<br />
d<sub>14</sub> = min(d<sub>14</sub>, d<sub>16</sub> + d<sub>64</sub>) = 1<br />
d<sub>15</sub> = min(d<sub>15</sub>, d<sub>16</sub> + d<sub>65</sub>) = 12<br />
d<sub>23</sub> = min(d<sub>23</sub>, d<sub>26</sub> + d<sub>63</sub>) = 8<br />
d<sub>24</sub> = min(d<sub>24</sub>, d<sub>26</sub> + d<sub>64</sub>) = 4<br />
d<sub>25</sub> = min(d<sub>25</sub>, d<sub>26</sub> + d<sub>65</sub>) = 9<br />
d<sub>34</sub> = min(d<sub>34</sub>, d<sub>36</sub> + d<sub>64</sub>) = 5<br />
d<sub>35</sub> = min(d<sub>35</sub>, d<sub>36</sub> + d<sub>65</sub>) = 7<br />
d<sub>45</sub> = min(d<sub>45</sub>, d<sub>46</sub> + d<sub>65</sub>) = 12<br />
La matriz de distancia después de esta iteración es:<br />
<dl><dd><img alt="\mathcal{W}_6 = \begin{bmatrix}
0 & 3 & 5 & 1 & 12 & 5\\
3 & 0 & 8 & 4 & 9 & 8\\
5 & 8 & 0 & 5 & 7 & 1\\
1 & 4 & 5 & 0 & 12 & 4\\
12 & 9 & 7 & 12 & 0 & 8\\
5 & 8 & 1 & 4 & 8 & 0\end{bmatrix}" class="tex" src="http://upload.wikimedia.org/math/c/a/0/ca05a03becdf5d2c7245e603b8a44e52.png" /></dd></dl>
Ya se han hecho todas las iteraciones posibles. Por tanto, el camino mínimo entre 2 vértices cualesquiera del <a href="http://es.wikipedia.org/wiki/Grafo" title="Grafo">grafo</a> será el obtenido en la matriz final. En este caso, el camino mínimo entre 3 y 4 vale 5.<br />
<br />
<div style="text-align: justify;">
<br /></div>
Sonnier Josehttp://www.blogger.com/profile/10471773210803344377noreply@blogger.com2tag:blogger.com,1999:blog-1103149321150022457.post-39269905051571951532013-02-13T19:13:00.002-08:002013-02-13T19:13:51.201-08:00Video Tutorial<a href="http://www.youtube.com/watch?v=rEp50y6Ul44">http://www.youtube.com/watch?v=rEp50y6Ul44</a><br />
<br />
<br />Sonnier Josehttp://www.blogger.com/profile/10471773210803344377noreply@blogger.com0