Grafos II

Floyd Warshall, Puntos de Articulación y Puentes

Floyd Warshall

Ruta más corta + DP

¿Qué debemos hacer cuando necesitamos conocer la información de la ruta más corta desde todos los vertices (V) del grafo?

Solución 1: Dijkstra

Ejecutar V llamados del algoritmo de Dijkstra

Costo: O( v^3 log V )

Solución 2: Bellman Ford

Ejecutar V llamados del algoritmo de Bellman Ford

Costo: O( v^4 )

Solución 3: Floyd Warshall ;)

Ejecutar 1 llamado al Algoritmo de Floyd Warshall

Costo: O( v^3 )

Condiciones

• El grafo debe estar almacenado en una matriz de adyacencia.
• Usarse en grafos cuya cantidad de vertices V <= 400

Floyd Warshall

                                              
static void FloydWarshall(){
    int i, j, k;

    for( k = 0; k < V; k++ ){
        for( i = 0; i < V; i++ ){
            for( j = 0; j < V; j++ ){
                adj[i][j] = Math.min( adj[i][j], adj[i][k] + adj[k][j] );
            }
        }
    }
}
                        
                    

Limpiar la Matriz de Adyacencia

                                              
static void init(){
    int i, j;

    for( i = 0; i < V; i++ ){
        adj[i] = new int[V];
        for( j = 0; j < V; j++ ){
            adj[i][j] = 1000000000;
        }
        adj[i][i] = 0;
    }
}
                        
                    

Puntos de Articulación y Puentes

DFS :3

Un Punto de Articulación en un grafo, es un vertice tal que al eliminarlo, produce un incremento en el número de componentes conexas.

Un Puente en un grafo, es una arista tal que al eliminarla, produce un incremento en el número de componentes conexas.

Vamos a introducir dos nuevos atributos al algoritmo DFS

• dfs_num: Almacena un contador cuando el vertice u es visitado por primera vez.
• dfs_low: Almacena el dfs_num más pequeño que es alcanzable desde la expansión del vertice u.

Puntos a tener en cuenta:

• Para grafos NO dirigidos
• Al comenzar el dfs_low(v) = dfs_num(v)
• No se actualizara el dfs_low(u) con un arco de "regreso" (u, v) si v es el padre de u
• Caso especial: La raiz del DFS es un punto de articulación si y solo si tiene más de un hijo.

Ejercicios propuestos