Algoritmo de Warshal

Encuentra si posible un camino entre cada uno de los vértices de la gráfica dirigida. Es decir no presenta las distancia entre los vértices
Se basa en un concepto llamado cerradura transitiva de la matriz de       adyacencia
El algoritmo de Warshall sirve para encontrar la cerradura transitiva de una relación binaria en el conjunto A. La clausura transitiva de una relación binaria es la relación binaria mas pequeña que siendo transitiva contenga el conjunto de pares de la relación binaria original.

CARACTERÍSTICAS DEL ALGORITMO DE WARSHALL
Es una representación de algoritmo Booleano
Cierre transitivo
Se obtiene una matriz de adyacencia
Cierre transitivo
Cierre transitivo de una relación binaria es encontrar la relación binaria más pequeña, que siendo esta transitiva contiene al conjunto de pares de la relación binaria original.

Matriz de Caminos
Es una matriz cuadrada P,
Que representa si hay o no camino Entre dos vértices Vi y Vj
UN POSIBLE ALGORITMO
Entre Vi y Vj puede haber caminoDirecto, cuando A[i][j] == 1, camino de long. 1



WARSHALL: MÁS EFICIENTE
El anterior algoritmo es poco eficiente, peor Cuando el grafo tiene muchos vértices Warshall propuso otro algoritmo mas eficiente
Calcular una secuencia de matrices cuadradas
De 0s(no hay camino) y 1s(hay camino)
P0, P1, P2, P3… PN
La diferencia entre Pk y Pk-1
Se basa añadir un vértice Vk-1 al análisis
Para saber y a través de Vk-1 hay camino entre V1 y Vj



Pseudocodigo

1 /* Suponemos que la función pesoArista devuelve el coste del camino que va de i a j
2    (infinito si no existe).
3    También suponemos que  es el número de vértices y pesoArista(i,i) = 0
4 */
5
6 int camino[][];
7 /* Una matriz bidimensional. En cada paso del algoritmo, camino[i][j] es el camino mínimo 
8    de i hasta j usando valores intermedios de (1..k-1). Cada camino[i][j] es inicializado a 
9    
10 */
11
12 procedimiento FloydWarshall ()
13    para k: = 0 hasta n − 1
14      
15          camino[i][j] = mín ( camino[i][j], camino[i][k]+camino[k][j])
16      
17    fin para

CODIGO C++

//ARSHAL
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
//#include "alloc.h"
#define MAXIMO 20
#define PR(x) printf ("%s",x)
#define SALTO printf ("\n")


int main() {
 int M[MAXIMO][MAXIMO],T[MAXIMO][MAXIMO];
 int nv,i;
 void listar_g (int g[][MAXIMO], int nv);
 int lea_grafo (int grafo[][MAXIMO]);
 void WARSHALL (int M[][MAXIMO], int T[][MAXIMO], int nv);
 nv = lea_grafo (M);
 listar_g (M ,nv);
 SALTO;
 getch();
 WARSHALL (M,T,nv);
 listar_g (T,nv);
 SALTO;
 getch();
}

void WARSHALL (int M[][MAXIMO], int T[][MAXIMO], int nv)
{
 int i,j,k;
 void listar_g (int g[][MAXIMO], int nv);
 void copiar (int a[][MAXIMO], int b[][MAXIMO],int nv);
 copiar (T, M, nv);
 for (k=1; k<=nv; k++) {
  for (i=1; i<=nv; i++) {
   if (i!=k) {
    if (T[i][k] == 1) {
     for (j=1; j<=nv; j++) {
      if (T[i][j] == 0)
       T[i][j] = T[k][j];
     }
    }
   }
  }
  SALTO;
  listar_g (T,nv);getch();
  SALTO;
 }
}




int lea_grafo (int grafo[][MAXIMO])
{
 int v,ad,i,j,n;
 int lea();
 PR("De numero de vertices...");
 SALTO;
 n = lea();
 for (i=1; i <= n; i++)
  for (j=1; j <=n; j++)
   grafo[i][j] = 0;
 PR ("Lea el primer vertice. 99 para terminar...");
 SALTO;
 v = lea();
 while (v != 99) {
  PR ("Lea el primer adjunto al vertice ");
  printf ("%d ",v);
  PR(". 99 para terminar");
  SALTO;
  ad = lea();
  while (ad != 99) {
   grafo [v][ad] = 1;
   PR ("Lea otro adjunto al vertice ");
   printf ("%d ",v);
   PR(". 99 para terminar");
   SALTO;
   ad = lea();
  }
  PR ("Lea otro vertice. 99 para terminar...");
  SALTO;
  v = lea();
 }
 return (n);
}

int lea() {
 char L[10];

 gets (L);
 return (atoi (L));
}


void listar_g (int g[][MAXIMO], int nv) {
 int i,j;

 for (i=1; i <= nv; i++) {
  for (j = 1; j <= nv; j++)
   printf ("%d ",g[i][j]);
  SALTO;
 }
}


void copiar (int a[][MAXIMO], int b[][MAXIMO],int nv) {
 int i,j;

 for (i=1; i<=nv; i++)
  for (j=1; j <= nv; j++)
   a[i][j] = b[i][j];
}