CODEWITHSUNDEEP
graph
Dip Chakraborty
Dip Chakraborty

Reputation: 67

find the node such sum of the minimum distances from that node to all other node is minimum

how i can find the node such sum of the minimum distances from that node to all other node is minimum in a undirected graph. i have traversed the graph with dfs.

i have found the minimum distance from a source node. what will be the strategy?

my try - 

import java.util.LinkedList;
import java.util.Scanner;
class Edge {

    int from;
    int to;
    long wt;
    Edge(int a, int b, long w)
    {
        from = a;
        to = b;
        wt = w;
    }
}
class Graph {

    LinkedList<Edge>[] adj_lis;
    int V;
    public static long[]val;
    Graph(int v)
    {
        this.V = v;
        adj_lis = new LinkedList[V];
        for (int i = 0; i < V; i++)
            adj_lis[i] = new LinkedList<>();
    }


    void add_edge(int to, int from, long wt)
    {
        adj_lis[from].add(
                new Edge(from, to, wt));
        adj_lis[to].add(
                new Edge(to, from, wt));
    }

    // DFS method to find distance

    void dfs(int v,
             int par,
             long sum,
             boolean[] visited)
    {
        val[v] = sum;
        visited[v] = true;
        for (Edge e : adj_lis[v]) {
            if (!visited[e.to])
                dfs(e.to,
                        v,
                        sum + e.wt,
                        visited);
        }
    }

}

Upvotes: 0

Views: 1132

Answers (1)

alidadar7676
alidadar7676

Reputation: 137

At first, DFS doesn't find the shortest path between two nodes and you should use BFS.

For finding the shortest paths in a weighted graph between all nodes, you can use Floyd Warshall algorithm. It returns a 2D array which array[i][j] is the size of the shortest path between node i and node j. So after that, you can calculate the sum of the row k in 2D array to find the sum of the minimum distances from node k to all other nodes. Do it for all rows and then find the minimum of them to detect the node in which the sum of the minimum distances from that node to all other nodes is minimum.

Upvotes: 1

Related Questions