Sesión 14

Vista previa del material en texto

UPN, PASIÓN POR
TRANSFORMAR VIDAS
SESIÓN 14: Teoría de grafos
Ing. Mitchell Blancas
ANALISIS DE ALGORITMOS Y ESTRATEGIAS DE PROGRAMACION
LOGRO DE LA SESIÓN
Al término de la sesión el estudiante aplica algoritmos sobre grafos en la solución de problemas propuestos y los representa a través de algoritmos.
¡Pregunta!
¿Qué algoritmos sobre grafos utilizamos a diario?
Algoritmo de Dijsktra
Sirve para encontrar el camino más corto de un vértice elegido a cualquier otro vértice del grafo.
0
Lima
2
Tacna
1
Ica
3
Ilo
4
Cuzco
12
10
8
8
15
20
El algoritmo de Dijsktra encontrará todas las distancias mínimas para ir de un vértice de origen (Lima) a todos los otros vértices (otras ciudades), por ejemplo si la ciudad origen es Lima, se obtendrá:
 Lima – Ica = 10 Km
 Lima – Tacna = 23 Km
 Lima – Ilo = 15 Km
 Lima – Cuzco = 12 Km
# include <iostream.h>
# include <iomanip.h>
# define N 25
# define MAX 1000000
struct EstadoVertice
{
 int ultimo;
 int distancia;
};
void leerMatCostos(int, int [ ][N]);
void impMatriz(int, int [ ][N]);
int minimo(int [ ], EstadoVertice [ ], int);
void caminoMinimos (int, EstadoVertice [ ], int [ ][N], int);
void main(void)
{
 int n, origen=0;
 int matPesos[N][N];
 EstadoVertice D[N];
 cout<<"Nro de vertices:"; cin>>n;
 leerMatCostos(n, matPesos);
 impMatriz(n, matPesos);
 caminoMinimos(origen, D, matPesos, n);
 for(int i=0;i<n;i++)
 {
 if ( origen!=i )
 {
 cout <<"El camino mas corto desde “
 <<origen<<" a "<<i<<" es "<<D[i].distancia;
 }
 cout<<endl;
 }
}
void leerMatCostos(int n, int matPesos[ ][N])
{
 int i,j, ncon, f, c;
 
 for (i=0; i<n; i++)
 for (j=0; j<n; j++)
 matPesos[i][j]=MAX;
 cout<<"Cantidad de conexiones:"; 
 cin>>ncon;
 
 for(i=0; i<ncon; i++)
 { 
 cout<<"Fila : "; cin>>f;
 cout<<"Columna: "; cin>>c;
 cout<<"Costo : "; cin>>matPesos[f][c];
 cout<<endl;
 } 
}
void impMatriz(int n, int matPesos[ ][N])
{
 int i,j;
 
 for (i=0; i<n; i++)
 {
 for (j=0; j<n; j++)
 cout<<setw(12)<<matPesos[i][j];
 cout<<endl;
 }
}
int minimo(int F[], EstadoVertice D[], int n)
{ int j, v, mx= MAX;
 for(j=1; j<n; j++)
 if( !F[j] && (mx>=D[j].distancia) )
 {
	mx=D[j].distancia;
	v=j;
 }
 return v;
}
void caminoMinimos( int origen, EstadoVertice D[ ], 
 int matPesos[ ][N], int n)
{ int v, w, i, F[N], s=origen; // vértice origen
 F[s]=1;
 for(i=1; i<n; i++)
 { F[i]=0;
 D[i].distancia = matPesos[0][i];
 D[i].ultimo = 0;
 }
 for(i=1; i<n; i++)
 { v=minimo(F, D, n);
 F[v] = 1;
 for(w=1; w<n; w++)
 {
 if(!F[w]) 
	if( (D[v].distancia + matPesos[v][w]) < D[w].distancia)
	{
	 D[w].distancia = D[v].distancia + matPesos[v][w];
	 D[w].ultimo = v;
	}
 }
 }
}
Robert W. Floyd
1936-2001
Algoritmo de Floyd
Encuentra el camino mínimo entre todos los pares de nodos, en una pasada. 
(Usa la programación dinámica pues cumple el principio de optimalidad)
# include <iostream>
# include <iomanip>
using namespace std;
# define INF 1.0E+38
# define N 5
void todoCaminoMinimo (double costes[ ][N], double D[ ][N], int traza[ ][N], int n)
{ int i, j, k;
 for(i=0; i<n; i++)
 for(j=0; j<n; j++)
 { D[i][j] = costes[i][j];
 traza[i][j]=-1;
 }
 for(i=0; i<n; i++)
 D[i][i] = 0;
 for(k=0; k<n; k++)
 for(i=0; i<n; i++)
 for(j=0; j<n; j++)
 if( D[i][k] + D[k][j] < D[i][j] )
 { D[i][j] = D[i][k] + D[k][j];
 traza[i][j]=k;
 }
}
void recuperaCamino( int vi, int vj,
 int traza[ ][N])
{
 int vk;
 vk=traza[vi][vj];
 if ( vk != -1 )
 {
 recuperaCamino(vi, vk, traza);
 cout<<vk<<" -> ";
 recuperaCamino(vk, vj, traza);
 }
}
void main(void)
{ double costes[ ][N]= 
 { { 0, 1, INF, INF, INF},
 { INF, 0, INF, 4, 7},
 { 3, 2, 0, INF, 4},
 { 6, INF, INF, 0, 2},
 { INF, INF, INF, 3, 0} };
 double D[N][N];
 int traza[N][N], vi, vj;
 todoCaminoMinimo (costes, D, traza, N);
 for(int i=0;i<N;i++)
 {
 for(int j=0; j<N; j++)
	cout <<setw(8)<<D[i][j]<<" ";
 cout<<endl;
 }
 cout<<endl<<endl;
 cout<<"Nodo inicial:"; cin>> vi;
 cout<<"Nodo final :"; cin>> vj;
 recuperaCamino(vi, vj, traza);
 cout<<endl;
}
Algoritmo de Warshall
Nos dice si existe camino entre dos pares de vertices.
void todoCaminoMinimo (int costes[ ][N], int D[ ][N], int n)
{
 int i, j, k;
 for(i=0; i<n; i++)
 for(j=0; j<n; j++)
 D[ i ][ j ] = costes[ i ][ j ];
 for(i=0; i<n; i++)
 D[ i ][ i ] = 0;
 for(k=0; k<n; k++)
 for(i=0; i<n; i++)
 for(j=0; j<n; j++)
 D[ i ][ j ] = D[ i ][ j ] || ( D[ i ][ k ] && D[ k ][ j ] );
}
Algoritmo de Prim
7
5
0
4
3
9
8
10
7
7
6
3
10
8
3
6
7
9
7
10
8
10
7
5
0
4
3
2
9
8
10
7
6
3
10
8
3
6
7
7
6
6
1
6
1
6
2
Permite obtener el árbol de expansión de coste mínimo
7
5
0
4
3
2
9
8
10
7
6
3
10
8
3
6
7
7
6
1
6
Arbol de expansión mínima
# include <iostream>
# include <iomanip>
using namespace std;
# define INF 1.0E+38
# define N 6
double arbolExpansion (double costos[ ][N], int n);
int main(void)
{
 double costos[ ][N]= 
 { 
 { 0, 2, 1, INF, 3, 6 },
 { 2, 0, 3, 2, INF, INF },
 { 1, 3, 0, 4, INF, INF },
 { INF, 2, 4, 0, INF, 5 },
 { 3, INF, INF, INF, 0, 4 },
 { 6, INF, INF, 5, 4, 0 }
 };
 cout<<"Costo :" << arbolExpansion (costos, N);
 cout<<endl;
}
3
0
1
4
2
2
3
6
3
5
1
4
4
5
2
Algoritmo de Prim
double arbolExpansion (double costos[ ][N], 
 int n)
{
 int i, j;
 double longMin, menor;
 int z;
 double costo[N];
 int masCerca[N];
 int W[N];
 for(i=0; i<n; i++)
 W[i]=0;
 longMin = 0;
 W[0] = 1;
 for(i=1; i<n; i++) {
 costo[i]=costos[0][i];
 masCerca[i] = 0;
 }
for(i=1; i<n; i++)
{
 menor= costo[1];
 z=1;
 for(j=2; j<n; j++)
 if(costo[j] <menor)
 {
 menor=costo[j];
 z=j;
 }
 longMin += menor;
 cout<<masCerca[z]<<" "<<z<<endl;
 W[z]=1;
 costo[z] = INF;
 for(j=1; j<n; j++)
 if(costos[z][j] < costo[j] && !W[j])
 {
 costo[j] = costos[z][j];
 masCerca[j] =z;
 }
 }
 return longMin;
}
Algoritmo de Prim
3
0
1
4
2
2
3
6
3
5
1
4
4
5
2
3
0
1
4
2
2
3
1
4
5
2
Algoritmos distribuidos
¡Gracias por su atención!