Dado un grafo no dirigido ponderado T que consta de Nodes valorados [0, N – 1] y una array Edges[][3] de tipo { u , v , w } que denota un borde entre los vértices u y v que tiene un peso w . La tarea es encontrar la suma de todos los pares de caminos más cortos en el árbol dado .
Ejemplos:
Entrada: N = 3, Edges[][] = {{0, 2, 15}, {1, 0, 90}}
Salida: 210
Explicación:
Suma de pesos de ruta entre Nodes 0 y 1 = 90
Suma de pesos de ruta entre los Nodes 0 y 2 = 15
Suma de los pesos de la ruta entre los Nodes 1 y 2 = 105
Por lo tanto, suma = 90 + 15 + 105Entrada: N = 4, Edges[][] = {{0, 1, 1}, {1, 2, 2}, {2, 3, 3}} Salida: 20 Explicación: Suma de pesos de
ruta entre
Nodes
0 y 1 = 1
Suma de pesos de camino entre Nodes 0 y 2 = 3
Suma de pesos de camino entre Nodes 0 y 3 = 6
Suma de pesos de camino entre Nodes 1 y 2 = 2
Suma de pesos de camino entre Nodes 1 y 3 = 5
Suma de pesos del camino entre los Nodes 2 y 3 = 3
Por lo tanto, suma = 1 + 3 + 6 + 2 + 5 + 3 = 20.
Enfoque ingenuo: el enfoque más simple es encontrar el camino más corto entre cada par de vértices utilizando el algoritmo Floyd Warshall . Después de calcular previamente el costo del camino más corto entre cada par de Nodes, imprima la suma de todos los caminos más cortos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
#define INF 99999
// Function that performs the Floyd
// Warshall to find all shortest paths
int floyd_warshall(int* graph, int V)
{
int dist[V][V], i, j, k;
// Initialize the distance matrix
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
dist[i][j] = *((graph + i * V) + j);
}
}
for (k = 0; k < V; k++) {
// Pick all vertices as
// source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as
// destination for the
// above picked source
for (j = 0; j < V; j++) {
// If vertex k is on the
// shortest path from i to
// j then update dist[i][j]
if (dist[i][k]
+ dist[k][j]
< dist[i][j]) {
dist[i][j]
= dist[i][k]
+ dist[k][j];
}
}
}
}
// Sum the upper diagonal of the
// shortest distance matrix
int sum = 0;
// Traverse the given dist[][]
for (i = 0; i < V; i++) {
for (j = i + 1; j < V; j++) {
// Add the distance
sum += dist[i][j];
}
}
// Return the final sum
return sum;
}
// Function to generate the tree
int sumOfshortestPath(int N, int E,
int edges[][3])
{
int g[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
g[i][j] = INF;
}
}
// Add edges
for (int i = 0; i < E; i++) {
// Get source and destination
// with weight
int u = edges[i][0];
int v = edges[i][1];
int w = edges[i][2];
// Add the edges
g[u][v] = w;
g[v][u] = w;
}
// Perform Floyd Warshal Algorithm
return floyd_warshall((int*)g, N);
}
// Driver code
int main()
{
// Number of Vertices
int N = 4;
// Number of Edges
int E = 3;
// Given Edges with weight
int Edges[][3]
= { { 0, 1, 1 }, { 1, 2, 2 },
{ 2, 3, 3 } };
// Function Call
cout << sumOfshortestPath(N, E, Edges);
return 0;
}
Java
// Java program for
// the above approach
class GFG{
static final int INF = 99999;
// Function that performs the Floyd
// Warshall to find all shortest paths
static int floyd_warshall(int[][] graph,
int V)
{
int [][]dist = new int[V][V];
int i, j, k;
// Initialize the distance matrix
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
dist[i][j] = graph[i][j];
}
}
for (k = 0; k < V; k++)
{
// Pick all vertices as
// source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as
// destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the
// shortest path from i to
// j then update dist[i][j]
if (dist[i][k] + dist[k][j] <
dist[i][j])
{
dist[i][j] = dist[i][k] +
dist[k][j];
}
}
}
}
// Sum the upper diagonal of the
// shortest distance matrix
int sum = 0;
// Traverse the given dist[][]
for (i = 0; i < V; i++)
{
for (j = i + 1; j < V; j++)
{
// Add the distance
sum += dist[i][j];
}
}
// Return the final sum
return sum;
}
// Function to generate the tree
static int sumOfshortestPath(int N, int E,
int edges[][])
{
int [][]g = new int[N][N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
g[i][j] = INF;
}
}
// Add edges
for (int i = 0; i < E; i++)
{
// Get source and destination
// with weight
int u = edges[i][0];
int v = edges[i][1];
int w = edges[i][2];
// Add the edges
g[u][v] = w;
g[v][u] = w;
}
// Perform Floyd Warshal Algorithm
return floyd_warshall(g, N);
}
// Driver code
public static void main(String[] args)
{
// Number of Vertices
int N = 4;
// Number of Edges
int E = 3;
// Given Edges with weight
int Edges[][] = {{0, 1, 1}, {1, 2, 2},
{2, 3, 3}};
// Function Call
System.out.print(
sumOfshortestPath(N, E, Edges));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach INF = 99999 # Function that performs the Floyd # Warshall to find all shortest paths def floyd_warshall(graph, V): dist = [[0 for i in range(V)] for i in range(V)] # Initialize the distance matrix for i in range(V): for j in range(V): dist[i][j] = graph[i][j] for k in range(V): # Pick all vertices as # source one by one for i in range(V): # Pick all vertices as # destination for the # above picked source for j in range(V): # If vertex k is on the # shortest path from i to # j then update dist[i][j] if (dist[i][k] + dist[k][j] < dist[i][j]): dist[i][j] = dist[i][k] + dist[k][j] # Sum the upper diagonal of the # shortest distance matrix sum = 0 # Traverse the given dist[][] for i in range(V): for j in range(i + 1, V): # Add the distance sum += dist[i][j] # Return the final sum return sum # Function to generate the tree def sumOfshortestPath(N, E,edges): g = [[INF for i in range(N)] for i in range(N)] # Add edges for i in range(E): # Get source and destination # with weight u = edges[i][0] v = edges[i][1] w = edges[i][2] # Add the edges g[u][v] = w g[v][u] = w # Perform Floyd Warshal Algorithm return floyd_warshall(g, N) # Driver code if __name__ == '__main__': # Number of Vertices N = 4 # Number of Edges E = 3 # Given Edges with weight Edges = [ [ 0, 1, 1 ], [ 1, 2, 2 ], [ 2, 3, 3 ] ] # Function Call print(sumOfshortestPath(N, E, Edges)) # This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
class GFG{
static readonly int INF = 99999;
// Function that performs the Floyd
// Warshall to find all shortest paths
static int floyd_warshall(int[,] graph,
int V)
{
int [,]dist = new int[V, V];
int i, j, k;
// Initialize the distance matrix
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
dist[i, j] = graph[i, j];
}
}
for (k = 0; k < V; k++)
{
// Pick all vertices as
// source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as
// destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the
// shortest path from i to
// j then update dist[i,j]
if (dist[i, k] + dist[k, j] <
dist[i, j])
{
dist[i, j] = dist[i, k] +
dist[k, j];
}
}
}
}
// Sum the upper diagonal of the
// shortest distance matrix
int sum = 0;
// Traverse the given dist[,]
for (i = 0; i < V; i++)
{
for (j = i + 1; j < V; j++)
{
// Add the distance
sum += dist[i, j];
}
}
// Return the readonly sum
return sum;
}
// Function to generate the tree
static int sumOfshortestPath(int N, int E,
int [,]edges)
{
int [,]g = new int[N, N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
g[i, j] = INF;
}
}
// Add edges
for (int i = 0; i < E; i++)
{
// Get source and destination
// with weight
int u = edges[i, 0];
int v = edges[i, 1];
int w = edges[i, 2];
// Add the edges
g[u, v] = w;
g[v, u] = w;
}
// Perform Floyd Warshal Algorithm
return floyd_warshall(g, N);
}
// Driver code
public static void Main(String[] args)
{
// Number of Vertices
int N = 4;
// Number of Edges
int E = 3;
// Given Edges with weight
int [,]Edges = {{0, 1, 1},
{1, 2, 2},
{2, 3, 3}};
// Function Call
Console.Write(sumOfshortestPath(N,
E, Edges));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for
// the above approach
let INF = 99999;
// Function that performs the Floyd
// Warshall to find all shortest paths
function floyd_warshall(graph,V)
{
let dist = new Array(V);
for(let i = 0; i < V; i++)
{
dist[i] = new Array(V);
}
let i, j, k;
// Initialize the distance matrix
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
dist[i][j] = graph[i][j];
}
}
for (k = 0; k < V; k++)
{
// Pick all vertices as
// source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as
// destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the
// shortest path from i to
// j then update dist[i][j]
if (dist[i][k] + dist[k][j] <
dist[i][j])
{
dist[i][j] = dist[i][k] +
dist[k][j];
}
}
}
}
// Sum the upper diagonal of the
// shortest distance matrix
let sum = 0;
// Traverse the given dist[][]
for (i = 0; i < V; i++)
{
for (j = i + 1; j < V; j++)
{
// Add the distance
sum += dist[i][j];
}
}
// Return the final sum
return sum;
}
// Function to generate the tree
function sumOfshortestPath(N,E,edges)
{
let g = new Array(N);
for (let i = 0; i < N; i++)
{
g[i] = new Array(N);
for (let j = 0; j < N; j++)
{
g[i][j] = INF;
}
}
// Add edges
for (let i = 0; i < E; i++)
{
// Get source and destination
// with weight
let u = edges[i][0];
let v = edges[i][1];
let w = edges[i][2];
// Add the edges
g[u][v] = w;
g[v][u] = w;
}
// Perform Floyd Warshal Algorithm
return floyd_warshall(g, N);
}
// Driver code
// Number of Vertices
let N = 4;
// Number of Edges
let E = 3;
// Given Edges with weight
let Edges = [[0, 1, 1], [1, 2, 2],
[2, 3, 3]];
// Function Call
document.write(
sumOfshortestPath(N, E, Edges));
// This code is contributed by patel2127
</script>
Producción:
20
Complejidad Temporal: O(N 3 ), donde N es el número de vértices.
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es usar el algoritmo DFS , usando el DFS , para cada vértice, el costo de visitar todos los demás vértices desde este vértice se puede encontrar en tiempo lineal. Siga los pasos a continuación para resolver el problema:
- Atraviese los Nodes 0 a N – 1 .
- Para cada Node i , encuentre la suma del costo de visitar cada otro vértice usando DFS donde la fuente será el Node i , y denotemos esta suma por S i .
- Ahora, calcule S = S 0 + S 1 + … + S N-1 . y divida S por 2 porque cada ruta se calcula dos veces.
- Después de completar los pasos anteriores, imprima el valor de la suma S obtenido.
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;
// Function that performs the DFS
// traversal to find cost to reach
// from vertex v to other vertexes
void dfs(int v, int p,
vector<pair<int, int>> t[],
int h, int ans[])
{
// Traverse the Adjacency list
// of u
for(pair<int, int> u : t[v])
{
if (u.first == p)
continue;
// Recursive Call
dfs(u.first, v, t, h + u.second, ans);
}
// Update ans[v]
ans[v] = h;
}
// Function to find the sum of
// weights of all paths
int solve(int n, int edges[][3])
{
// Stores the Adjacency List
vector<pair<int, int>> t[n];
// Store the edges
for(int i = 0; i < n - 1; i++)
{
t[edges[i][0]].push_back({edges[i][1],
edges[i][2]});
t[edges[i][1]].push_back({edges[i][0],
edges[i][2]});
}
// sum is the answer
int sum = 0;
// Calculate sum for each vertex
for(int i = 0; i < n; i++)
{
int ans[n];
// Perform the DFS Traversal
dfs(i, -1, t, 0, ans);
// Sum of distance
for(int j = 0; j < n; j++)
sum += ans[j];
}
// Return the final sum
return sum / 2;
}
// Driver Code
int main()
{
// No of vertices
int N = 4;
// Given Edges
int edges[][3] = { { 0, 1, 1 },
{ 1, 2, 2 },
{ 2, 3, 3 } };
// Function Call
cout << solve(N, edges) << endl;
return 0;
}
// This code is contributed by pratham76
Java
// Java program for the above approach
import java.io.*;
import java.awt.*;
import java.io.*;
import java.util.*;
@SuppressWarnings("unchecked")
class GFG {
// Function that performs the DFS
// traversal to find cost to reach
// from vertex v to other vertexes
static void dfs(int v, int p,
ArrayList<Point> t[],
int h, int ans[])
{
// Traverse the Adjacency list
// of u
for (Point u : t[v]) {
if (u.x == p)
continue;
// Recursive Call
dfs(u.x, v, t, h + u.y, ans);
}
// Update ans[v]
ans[v] = h;
}
// Function to find the sum of
// weights of all paths
static int solve(int n, int edges[][])
{
// Stores the Adjacency List
ArrayList<Point> t[]
= new ArrayList[n];
for (int i = 0; i < n; i++)
t[i] = new ArrayList<>();
// Store the edges
for (int i = 0; i < n - 1; i++) {
t[edges[i][0]].add(
new Point(edges[i][1],
edges[i][2]));
t[edges[i][1]].add(
new Point(edges[i][0],
edges[i][2]));
}
// sum is the answer
int sum = 0;
// Calculate sum for each vertex
for (int i = 0; i < n; i++) {
int ans[] = new int[n];
// Perform the DFS Traversal
dfs(i, -1, t, 0, ans);
// Sum of distance
for (int j = 0; j < n; j++)
sum += ans[j];
}
// Return the final sum
return sum / 2;
}
// Driver Code
public static void main(String[] args)
{
// No of vertices
int N = 4;
// Given Edges
int edges[][]
= new int[][] { { 0, 1, 1 },
{ 1, 2, 2 },
{ 2, 3, 3 } };
// Function Call
System.out.println(solve(N, edges));
}
}
Python3
# Python3 program for the above approach # Function that performs the DFS # traversal to find cost to reach # from vertex v to other vertexes def dfs(v, p, t, h, ans): # Traverse the Adjacency list # of u for u in t[v]: if (u[0] == p): continue # Recursive Call dfs(u[0], v, t, h + u[1], ans) # Update ans[v] ans[v] = h # Function to find the sum of # weights of all paths def solve(n, edges): # Stores the Adjacency List t = [[] for i in range(n)] # Store the edges for i in range(n - 1): t[edges[i][0]].append([edges[i][1], edges[i][2]]) t[edges[i][1]].append([edges[i][0], edges[i][2]]) # sum is the answer sum = 0 # Calculate sum for each vertex for i in range(n): ans = [0 for i in range(n)] # Perform the DFS Traversal dfs(i, -1, t, 0, ans) # Sum of distance for j in range(n): sum += ans[j] # Return the final sum return sum // 2 # Driver Code if __name__ == "__main__": # No of vertices N = 4 # Given Edges edges = [ [ 0, 1, 1 ], [ 1, 2, 2 ], [ 2, 3, 3 ] ] # Function Call print(solve(N, edges)) # This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that performs the DFS
// traversal to find cost to reach
// from vertex v to other vertexes
static void dfs(int v, int p,
List<Tuple<int, int>> []t,
int h, int []ans)
{
// Traverse the Adjacency list
// of u
foreach(Tuple<int, int> u in t[v])
{
if (u.Item1 == p)
continue;
// Recursive call
dfs(u.Item1, v, t,
h + u.Item2, ans);
}
// Update ans[v]
ans[v] = h;
}
// Function to find the sum of
// weights of all paths
static int solve(int n, int [,]edges)
{
// Stores the Adjacency List
List<Tuple<int,
int>> []t = new List<Tuple<int,
int>>[n];
for(int i = 0; i < n; i++)
t[i] = new List<Tuple<int, int>>();
// Store the edges
for(int i = 0; i < n - 1; i++)
{
t[edges[i, 0]].Add(
new Tuple<int, int>(edges[i, 1],
edges[i, 2]));
t[edges[i, 1]].Add(
new Tuple<int, int>(edges[i, 0],
edges[i, 2]));
}
// sum is the answer
int sum = 0;
// Calculate sum for each vertex
for(int i = 0; i < n; i++)
{
int []ans = new int[n];
// Perform the DFS Traversal
dfs(i, -1, t, 0, ans);
// Sum of distance
for(int j = 0; j < n; j++)
sum += ans[j];
}
// Return the readonly sum
return sum / 2;
}
// Driver Code
public static void Main(String[] args)
{
// No of vertices
int N = 4;
// Given Edges
int [,]edges = new int[,] { { 0, 1, 1 },
{ 1, 2, 2 },
{ 2, 3, 3 } };
// Function call
Console.WriteLine(solve(N, edges));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function that performs the DFS
// traversal to find cost to reach
// from vertex v to other vertexes
function dfs(v, p, t, h, ans)
{
// Traverse the Adjacency list
// of u
for(let u = 0; u < t[v].length; u++)
{
if (t[v][u][0] == p)
continue;
// Recursive Call
dfs(t[v][u][0], v, t,
h + t[v][u][1], ans);
}
// Update ans[v]
ans[v] = h;
}
// Function to find the sum of
// weights of all paths
function solve(n, edges)
{
// Stores the Adjacency List
let t = new Array(n);
for(let i = 0; i < n; i++)
t[i] = [];
// Store the edges
for(let i = 0; i < n - 1; i++)
{
t[edges[i][0]].push([edges[i][1],
edges[i][2]]);
t[edges[i][1]].push([edges[i][0],
edges[i][2]]);
}
// Sum is the answer
let sum = 0;
// Calculate sum for each vertex
for(let i = 0; i < n; i++)
{
let ans = new Array(n);
// Perform the DFS Traversal
dfs(i, -1, t, 0, ans);
// Sum of distance
for(let j = 0; j < n; j++)
sum += ans[j];
}
// Return the final sum
return sum / 2;
}
// Driver Code
let N = 4;
let edges = [ [ 0, 1, 1 ],
[ 1, 2, 2 ],
[ 2, 3, 3 ] ];
document.write(solve(N, edges));
// This code is contributed by unknown2108
</script>
Producción:
20
Complejidad Temporal: O(N 2 ), donde N es el número de vértices.
Espacio Auxiliar: O(N)