Suma de todos los pares de caminos más cortos en un árbol

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 + 105

Entrada: 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: 

  1. Atraviese los Nodes 0 a N – 1 .
  2. 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 .
  3. Ahora, calcule S = S 0 + S 1 + … + S N-1 . y divida S por 2 porque cada ruta se calcula dos veces.
  4. 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)

Publicación traducida automáticamente

Artículo escrito por man_preet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *