CODEWITHSUNDEEP
algorithmgraphtreeminimum
Mohammad Abdollahzadeh
Mohammad Abdollahzadeh

Reputation: 420

how can i make a optimal tree which some condition

we have a weighted graph we want to make an optimal tree with following condition:

1) tree should contain all vertex in graph

2) all of tree edges should be in graph

3) start from vertex U and reach any other vertex with minimum path.

with the initial graph and the condition we want to make a tree with minimum weight.

ex:

input

6 8

1 2 30

1 3 20

2 3 50

4 2 100

2 5 40

3 5 10

3 6 50

5 6 60

4

output: 230

explanation: we have 6 vertexs and 8 edges.after that we have 8 line with tree number. for example (2 3 50) says that vertex 2 is connected with vertex 3 with weight 50.

and at the end we have a number show the start vertex.

so if we start from vertex 4 and reach all of other vertex with minimum path, we can have a tree with sum weight of 230

Upvotes: 0

Views: 47

Answers (1)

Sanket Makani
Sanket Makani

Reputation: 2489

You can use Dijkstra's algorithm with U as a starting node. It will give you shortest distance to all the vertices from U. If you consider only those edges which are used in the calculation of the shortest distance to all the vertices, You will get the required tree.

Now to get all the edges, You need to do some modifications in the algorithm. You need to maintain a parent array which keeps an information about the vertex on which the current vertex depends(While calculating the shortest distance).

For example, We have two vertices U and V and distance to all the vertices from some source S is stored in distance[] array. Now suppose we have an edge E in between U and V with weight W and condition distance[U] > distance[V] + W gets satisfied, then parent of U will be V as distance[U] now depends on distance[V].

So we will add one more step in the algorithm where we update the distance. Initially parent[source] will be source itself as it doesn't depend on any other vertex.

Now at the end, To get all the edges, You need to iterate through the parent array and print index <-> parent[index].

Sample Code in Java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class ModifiedDijkstra {
    public static final long INF = (long) 1e15;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int totalVertices = sc.nextInt();
        int totalEdges = sc.nextInt();

        ArrayList<Edge> adjacencyList[] = new ArrayList[totalVertices + 1];

        for (int i = 1; i <= totalVertices; i++)
            adjacencyList[i] = new ArrayList<>();

        for (int i = 0; i < totalEdges; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            long weight = sc.nextInt();

            adjacencyList[u].add(new Edge(v, weight));
            adjacencyList[v].add(new Edge(u, weight));
        }

        int source = sc.nextInt();   //Source Index
        long distance[] = new long[totalVertices + 1];
        long edgesWeights[] = new long[totalVertices + 1];
        Arrays.fill(distance, INF);

        int parent[] = new int[totalVertices + 1];
        distance[source] = 0;
        parent[source] = source;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(source);

        while (!queue.isEmpty()) {
            int currVertex = queue.poll();

            for (Edge edge : adjacencyList[currVertex]) {
                if (distance[edge.endVertex] > distance[currVertex] + edge.weight) {
                    distance[edge.endVertex] = distance[currVertex] + edge.weight;
                    parent[edge.endVertex] = currVertex;
                    edgesWeights[edge.endVertex] = edge.weight;
                    queue.add(edge.endVertex);
                }
            }
        }

        System.out.println("TREE : ");

        long edgesSum = 0;

        for (int i = 1; i <= totalVertices; i++) {
            if (parent[i] == i) //source
                continue;

            //Vertex1 <-> Vertex2 : Weight
            System.out.println(i + " <-> " + parent[i] + " : " + edgesWeights[i]);
            edgesSum += edgesWeights[i];
        }

        System.out.println("Sum of the weights of all edges is : " + edgesSum);


    }
}

class Edge {
    int endVertex;
    long weight;

    public Edge(int endVertex, long weight) {
        this.endVertex = endVertex;
        this.weight = weight;
    }
}

Input:

6 8

1 2 30

1 3 20

2 3 50

4 2 100

2 5 40

3 5 10

3 6 50

5 6 60

4

Output:

TREE : 
1 <-> 2 : 30
2 <-> 4 : 100
3 <-> 2 : 50
5 <-> 2 : 40
6 <-> 3 : 50
Sum of the weights of all edges is : 270

Upvotes: 1

Related Questions