Dado un gráfico de array de adyacencia [][] de un gráfico ponderado que consta de N Nodes y pesos positivos, la tarea de cada componente conectado del gráfico es encontrar el máximo entre todas las distancias más cortas posibles entre cada par de Nodes .
Ejemplos:
Aporte:
Producción:
8 0 11
Explicación : hay tres componentes en el gráfico, a saber, a, b, c. En el componente (a) los caminos más cortos son los siguientes:
- La distancia más corta entre 3 y 4 es de 5 unidades.
- La distancia más corta entre 3 y 1 es 1+5=6 unidades.
- La distancia más corta entre 3 y 5 es 5+3=8 unidades.
- La distancia más corta entre 1 y 4 es 1 unidad.
- La distancia más corta entre 1 y 5 es 1+3=4 unidades.
- La distancia más corta entre 4 y 5 es de 3 unidades.
De estas distancias más cortas:
La distancia máxima más corta en el componente (a) es de 8 unidades entre el Node 3 y el Node 5.
De manera similar,
la distancia máxima más corta en el componente (b) es de 0 unidades .
La distancia máxima más corta en el componente (c) es de 11 unidades entre los Nodes 2 y 6.Aporte:
Producción:
7
Explicación: Dado que solo hay un componente con 2 Nodes que tienen un borde entre ellos de distancia 7. Por lo tanto, la respuesta será 7.
Enfoque: este problema dado se puede resolver encontrando los componentes conectados en el gráfico usando DFS y almacenando los componentes en una lista de listas . El algoritmo de Floyd Warshall se puede utilizar para encontrar las rutas más cortas de todos los pares en cada componente conectado que se basa en la programación dinámica . Después de obtener las distancias más cortas de todos los pares posibles en el gráfico, encuentre las distancias más cortas máximas para todos y cada uno de los componentes del gráfico . Siga los pasos a continuación para resolver el problema:
- Defina una función maxInThisComponent(vector<int> componente, vector<vector<int>> gráfico) y realice los siguientes pasos:
- Inicialice la variable maxDistance como INT_MIN y n como el tamaño del componente.
- Itere sobre el rango [0, n) usando la variable i y realice las siguientes tareas:
- Itere sobre el rango [i+1, n) usando la variable j y actualice el valor de maxDistance como el máximo de maxDistance o graph[component[i]][component[j]] .
- Devuelve el valor de maxDistance como respuesta.
- Inicialice un vector visitado de tamaño N e inicialice los valores como falsos .
- Inicializa los vectores , por ejemplo, components[][] y temp[] para almacenar cada componente del gráfico.
- Usando la primera búsqueda en profundidad (DFS), busque todos los componentes y guárdelos en el vector components[][] .
- Ahora, llame a la función floydWarshall(graph, V) para implementar el algoritmo de Floyd Warshall para encontrar la distancia más corta entre todos los pares de un componente de un gráfico.
- Inicializa un vector result[] para almacenar el resultado.
- Inicialice la variable numOfComp como el tamaño de los componentes del vector [][].
- Itere sobre el rango [0, numOfComp) usando la variable i y llame a la función maxInThisComponent(components[i], graph) y almacene el valor que devuelve en el vector result[] .
- Después de realizar los pasos anteriores, imprima los valores del vector result[] como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Below dfs function will be used to
// get the connected components of a
// graph and stores all the connected
// nodes in the vector component
void dfs(int src, vector<bool>& visited,
vector<vector<int> >& graph,
vector<int>& component, int N)
{
// Mark this vertex as visited
visited[src] = true;
// Put this node in component vector
component.push_back(src);
// For all other vertices in graph
for (int dest = 0; dest < N; dest++) {
// If there is an edge between
// src and dest i.e., the value
// of graph[u][v]!=INT_MAX
if (graph[src][dest] != INT_MAX) {
// If we haven't visited dest
// then recursively apply
// dfs on dest
if (!visited[dest])
dfs(dest, visited, graph,
component, N);
}
}
}
// Below is the Floyd Warshall Algorithm
// which is based on Dynamic Programming
void floydWarshall(
vector<vector<int> >& graph, int N)
{
// For every vertex of graph find
// the shortest distance with
// other vertices
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// Taking care of integer
// overflow
if (graph[i][k] != INT_MAX
&& graph[k][j] != INT_MAX) {
// Update distance between
// vertex i and j if choosing
// k as an intermediate vertex
// make a shorter distance
if (graph[i][k] + graph[k][j]
< graph[i][j])
graph[i][j]
= graph[i][k] + graph[k][j];
}
}
}
}
}
// Function to find the maximum shortest
// path distance in a component by checking
// the shortest distances between all
// possible pairs of nodes
int maxInThisComponent(vector<int>& component,
vector<vector<int> >& graph)
{
int maxDistance = INT_MIN;
int n = component.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
maxDistance
= max(maxDistance,
graph[component[i]][component[j]]);
}
}
// If the maxDistance is still INT_MIN
// then return 0 because this component
// has a single element
return (maxDistance == INT_MIN
? 0
: maxDistance);
}
// Below function uses above two method
// to get the maximum shortest distances
// in each component of the graph the
// function returns a vector, where each
// element denotes maximum shortest path
// distance for a component
vector<int> maximumShortesDistances(
vector<vector<int> >& graph, int N)
{
// Find the connected components
vector<bool> visited(N, false);
vector<vector<int> > components;
// For storing the nodes in a
// particular component
vector<int> temp;
// Now for each unvisited node run
// the dfs to get the connected
// component having this unvisited node
for (int i = 0; i < N; i++) {
if (!visited[i]) {
// First of all clear the temp
temp.clear();
dfs(i, visited, graph, temp, N);
components.push_back(temp);
}
}
// Now for all-pair find the shortest
// path distances using Floyd Warshall
floydWarshall(graph, N);
// Now for each component find the
// maximum shortest distance and
// store it in result
vector<int> result;
int numOfComp = components.size();
int maxDistance;
for (int i = 0; i < numOfComp; i++) {
maxDistance
= maxInThisComponent(components[i], graph);
result.push_back(maxDistance);
}
return result;
}
// Driver Code
int main()
{
int N = 8;
const int inf = INT_MAX;
// Adjacency Matrix for the first
// graph in the examples
vector<vector<int> > graph1 = {
{ 0, inf, 9, inf, inf, inf, 3, inf },
{ inf, 0, inf, 10, 1, 8, inf, inf },
{ 9, inf, 0, inf, inf, inf, 11, inf },
{ inf, 10, inf, 0, 5, 13, inf, inf },
{ inf, 1, inf, 5, 0, 3, inf, inf },
{ 8, inf, inf, 13, 3, 0, inf, inf },
{ 3, inf, 11, inf, inf, inf, 0, inf },
{ inf, inf, inf, inf, inf, inf, inf, 0 },
};
// Find the maximum shortest distances
vector<int> result1
= maximumShortesDistances(graph1, N);
// Printing the maximum shortest path
// distances for each components
for (int mx1 : result1)
cout << mx1 << ' ';
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
public class Main {
static boolean[] visited;
// For storing the connected components
static ArrayList <ArrayList <Integer> > components;
// Below dfs function will be used to
// get the connected components of a
// graph and stores all the connected
// nodes in the vector component
static void dfs(int[][] graph, ArrayList<Integer> temp,int src, int N)
{
// Mark this vertex as visited
visited[src] = true;
// Put this node in component vector
temp.add(src);
// For all other vertices in graph
for (int dest = 0; dest < N; dest++) {
// If there is an edge between
// src and dest i.e., the value
// of graph[u][v]!=Integer.MAX_VALUE
if (graph[src][dest] != Integer.MAX_VALUE) {
// If we haven't visited dest
// then recursively apply
// dfs on dest
if (!visited[dest])
dfs(graph, temp, dest, N);
}
}
}
// Below is the Floyd Warshall Algorithm
// which is based on Dynamic Programming
static void floydWarshall(int[][] graph, int N)
{
// For every vertex of graph find
// the shortest distance with
// other vertices
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// Taking care of integer
// overflow
if (graph[i][k] != Integer.MAX_VALUE
&& graph[k][j] != Integer.MAX_VALUE) {
// Update distance between
// vertex i and j if choosing
// k as an intermediate vertex
// make a shorter distance
if (graph[i][k] + graph[k][j]
< graph[i][j])
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
}
// Function to find the maximum shortest
// path distance in a component by checking
// the shortest distances between all
// possible pairs of nodes
static int maxInThisComponent(int[][] graph, ArrayList <Integer> component)
{
int maxDistance = Integer.MIN_VALUE;
int n = component.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
maxDistance
= Math.max(maxDistance,
graph[component.get(i)][component.get(j)]);
}
}
// If the maxDistance is still Integer.MIN_VALUE
// then return 0 because this component
// has a single element
return (maxDistance == Integer.MIN_VALUE
? 0
: maxDistance);
}
// Below function uses above two method
// to get the maximum shortest distances
// in each component of the graph the
// function returns a vector, where each
// element denotes maximum shortest path
// distance for a component
static ArrayList <Integer> maximumShortesDistances(int[][] graph, int N)
{
visited = new boolean[N];
Arrays.fill(visited, false);
// Find the connected components
components = new ArrayList <ArrayList<Integer> > ();
// Now for each unvisited node run
// the dfs to get the connected
// component having this unvisited node
for (int i = 0; i < N; i++) {
if (!visited[i] ) {
// For storing the nodes in a
// particular component
ArrayList<Integer> temp = new ArrayList<Integer> ();
dfs(graph, temp, i, N);
components.add(temp);
}
}
// Now for all-pair find the shortest
// path distances using Floyd Warshall
floydWarshall(graph, N);
// Now for each component find the
// maximum shortest distance and
// store it in result
ArrayList <Integer> result = new ArrayList <Integer> ();
int numOfComp = components.size();
int maxDistance;
for (int i = 0; i < numOfComp; i++) {
maxDistance
= maxInThisComponent(graph, components.get(i));
result.add(maxDistance);
}
return result;
}
// Driver Code
public static void main(String args[]) {
int N = 8;
final int inf = Integer.MAX_VALUE;
// Adjacency Matrix for the first
// graph in the examples
int[][] graph = {
{ 0, inf, 9, inf, inf, inf, 3, inf },
{ inf, 0, inf, 10, 1, 8, inf, inf },
{ 9, inf, 0, inf, inf, inf, 11, inf },
{ inf, 10, inf, 0, 5, 13, inf, inf },
{ inf, 1, inf, 5, 0, 3, inf, inf },
{ 8, inf, inf, 13, 3, 0, inf, inf },
{ 3, inf, 11, inf, inf, inf, 0, inf },
{ inf, inf, inf, inf, inf, inf, inf, 0 },
};
// Find the maximum shortest distances
ArrayList <Integer> result1
= maximumShortesDistances(graph, N);
// Printing the maximum shortest path
// distances for each components
for (int mx1 : result1)
System.out.print(mx1 + " ");
}
}
// This code has been contributed by Sachin Sahara (sachin801)
Python3
## Python program for the above approach:
INT_MAX = 9223372036854775807
INT_MIN = -9223372036854775808
## Below dfs function will be used to
## get the connected components of a
## graph and stores all the connected
## nodes in the vector component
def dfs(src, visited, graph, component, N):
## Mark this vertex as visited
visited[src] = True
## Put this node in component vector
component.append(src);
## For all other vertices in graph
for dest in range(0, N):
## If there is an edge between
## src and dest i.e., the value
## of graph[u][v]!=INT_MAX
if (graph[src][dest] != INT_MAX):
## If we haven't visited dest
## then recursively apply
## dfs on dest
if not visited[dest]:
dfs(dest, visited, graph, component, N);
## Below is the Floyd Warshall Algorithm
## which is based on Dynamic Programming
def floydWarshall(graph, N):
## For every vertex of graph find
## the shortest distance with
## other vertices
for k in range(0, N):
for i in range(0, N):
for j in range(0, N):
## Taking care of integer
## overflow
if (graph[i][k] != INT_MAX and graph[k][j] != INT_MAX):
## Update distance between
## vertex i and j if choosing
## k as an intermediate vertex
## make a shorter distance
if (graph[i][k] + graph[k][j] < graph[i][j]):
graph[i][j] = graph[i][k] + graph[k][j];
## Function to find the maximum shortest
## path distance in a component by checking
## the shortest distances between all
## possible pairs of nodes
def maxInThisComponent(component, graph):
maxDistance = INT_MIN;
n = len(component);
for i in range(0, n):
for j in range(i+1, n):
maxDistance = max(maxDistance, graph[component[i]][component[j]])
## If the maxDistance is still INT_MIN
## then return 0 because this component
## has a single element
if maxDistance == INT_MIN:
return 0
return maxDistance
## Below function uses above two method
## to get the maximum shortest distances
## in each component of the graph the
## function returns a vector, where each
## element denotes maximum shortest path
## distance for a component
def maximumShortesDistances(graph, N):
## Find the connected components
visited = []
for i in range(0, N):
visited.append(False)
components = []
## Now for each unvisited node run
## the dfs to get the connected
## component having this unvisited node
for i in range(0, N):
if not visited[i]:
## For storing the nodes in a
## particular component
temp = []
dfs(i, visited, graph, temp, N)
components.append(temp)
## Now for all-pair find the shortest
## path distances using Floyd Warshall
floydWarshall(graph, N)
## Now for each component find the
## maximum shortest distance and
## store it in result
result = []
numOfComp = len(components)
maxDistance = 0
for i in range(0, numOfComp):
maxDistance = maxInThisComponent(components[i], graph)
result.append(maxDistance)
return result
## Driver code
if __name__=='__main__':
N = 8
inf = INT_MAX;
## Adjacency Matrix for the first
## graph in the examples
graph1 = [
[ 0, inf, 9, inf, inf, inf, 3, inf ],
[ inf, 0, inf, 10, 1, 8, inf, inf ],
[ 9, inf, 0, inf, inf, inf, 11, inf ],
[ inf, 10, inf, 0, 5, 13, inf, inf ],
[ inf, 1, inf, 5, 0, 3, inf, inf ],
[ 8, inf, inf, 13, 3, 0, inf, inf ],
[ 3, inf, 11, inf, inf, inf, 0, inf ],
[ inf, inf, inf, inf, inf, inf, inf, 0 ],
];
## Find the maximum shortest distances
result1 = maximumShortesDistances(graph1, N);
## Printing the maximum shortest path
## distances for each components
for mx1 in result1:
print(mx1, end = " ")
print("")
# This code is contributed by subhamgoyal2014.
Javascript
<script>
// Javascript program for the above approach
// Below dfs function will be used to
// get the connected components of a
// graph and stores all the connected
// nodes in the vector component
function dfs(src, visited, graph, component, N)
{
// Mark this vertex as visited
visited[src] = true;
// Put this node in component vector
component.push(src);
// For all other vertices in graph
for (let dest = 0; dest < N; dest++)
{
// If there is an edge between
// src and dest i.e., the value
// of graph[u][v]!=INT_MAX
if (graph[src][dest] != Number.MAX_SAFE_INTEGER)
{
// If we haven't visited dest
// then recursively apply
// dfs on dest
if (!visited[dest]) dfs(dest, visited, graph, component, N);
}
}
}
// Below is the Floyd Warshall Algorithm
// which is based on Dynamic Programming
function floydWarshall(graph, N)
{
// For every vertex of graph find
// the shortest distance with
// other vertices
for (let k = 0; k < N; k++)
{
for (let i = 0; i < N; i++)
{
for (let j = 0; j < N; j++)
{
// Taking care of integer
// overflow
if (graph[i][k] != Number.MAX_SAFE_INTEGER && graph[k][j] != Number.MAX_SAFE_INTEGER)
{
// Update distance between
// vertex i and j if choosing
// k as an intermediate vertex
// make a shorter distance
if (graph[i][k] + graph[k][j] < graph[i][j])
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
}
// Function to find the maximum shortest
// path distance in a component by checking
// the shortest distances between all
// possible pairs of nodes
function maxInThisComponent(component, graph) {
let maxDistance = Number.MIN_SAFE_INTEGER;
let n = component.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
maxDistance = Math.max(maxDistance, graph[component[i]][component[j]]);
}
}
// If the maxDistance is still INT_MIN
// then return 0 because this component
// has a single element
return maxDistance == Number.MIN_SAFE_INTEGER ? 0 : maxDistance;
}
// Below function uses above two method
// to get the maximum shortest distances
// in each component of the graph the
// function returns a vector, where each
// element denotes maximum shortest path
// distance for a component
function maximumShortesDistances(graph, N) {
// Find the connected components
let visited = new Array(N).fill(false);
let components = new Array();
// For storing the nodes in a
// particular component
let temp = [];
// Now for each unvisited node run
// the dfs to get the connected
// component having this unvisited node
for (let i = 0; i < N; i++) {
if (!visited[i]) {
// First of all clear the temp
temp = [];
dfs(i, visited, graph, temp, N);
components.push(temp);
}
}
// Now for all-pair find the shortest
// path distances using Floyd Warshall
floydWarshall(graph, N);
// Now for each component find the
// maximum shortest distance and
// store it in result
let result = [];
let numOfComp = components.length;
let maxDistance;
for (let i = 0; i < numOfComp; i++) {
maxDistance = maxInThisComponent(components[i], graph);
result.push(maxDistance);
}
return result;
}
// Driver Code
let N = 8;
const inf = Number.MAX_SAFE_INTEGER;
// Adjacency Matrix for the first
// graph in the examples
let graph1 = [
[0, inf, 9, inf, inf, inf, 3, inf],
[inf, 0, inf, 10, 1, 8, inf, inf],
[9, inf, 0, inf, inf, inf, 11, inf],
[inf, 10, inf, 0, 5, 13, inf, inf],
[inf, 1, inf, 5, 0, 3, inf, inf],
[8, inf, inf, 13, 3, 0, inf, inf],
[3, inf, 11, inf, inf, inf, 0, inf],
[inf, inf, inf, inf, inf, inf, inf, 0],
];
// Find the maximum shortest distances
let result1 = maximumShortesDistances(graph1, N);
// Printing the maximum shortest path
// distances for each components
for (mx1 of result1) document.write(mx1 + " ");
// This code is contributed by gfgking.
</script>
Producción
11 8 0
Complejidad temporal: O(N 3 ), donde N es el número de vértices del gráfico.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sinhadiptiprakash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA