Given n electric components and m electric wires to connect them where each wire has a length. Find the optimized wire length between the two components.
Example :
Input : Source = A
Destination = C
Output: 4
Explanation: There are five different paths from node A to node C i.e., A->B->C, A->B->D->C, A->D->C, A->E->D->C, A->D->B->C. But the path with smallest or optimized length is A->E->D->C with length as 4.
Approach:
Given n components and m wires constitute an undirected weighted graph. The task is to calculate the optimized length between two components i.e., the minimum length between the two components. The problem is an application of Dijkstra’s algorithm. Since the source is available, the shortest length from the source to all nodes can be calculated using Dijkstra’s algorithm. This will give the shortest possible length between the given node source and all other nodes as an array. Now, the shortest length can be given from the source to destination using this array. Let’s understand this with the help of an example.
Example :
Input: Source = A
Destination = D
Output: 9
Explanation: Use Dijkstra’s algorithm to calculate shortest length from source A to all other nodes.
Vertex Distance from source
A 0
B 4
C 5
D 9
E 5
F 6
G 8
The shortest length can be found for any component from source A. Final answer will be the shortest length from A to D i.e., 9.
Below is the implementation of the above approach:
Java
// Java program for implementation// of above approachimport java.util.*;class GFG { // n is no. of nodes and m is no. of edges public static int n, m; // adjacency list representation of graph public static List<List<Node> > graph = new ArrayList<List<Node> >(); // source and destination points for shortest path public static int src, dest; static class Node { // node's label public int label; // length of edge to this node public int length; public Node(int v, int w) { label = v; length = w; } } // Driver program public static void main(String[] args) throws Exception { n = 5; m = 7; // Initialize adjacency list structure // to empty lists: for (int i = 0; i <= n; i++) { List<Node> item = new ArrayList<Node>(); graph.add(item); } graph.get(1).add(new Node(2, 2)); graph.get(2).add(new Node(1, 2)); graph.get(1).add(new Node(4, 4)); graph.get(4).add(new Node(1, 4)); graph.get(1).add(new Node(5, 2)); graph.get(5).add(new Node(1, 2)); graph.get(4).add(new Node(5, 1)); graph.get(5).add(new Node(4, 1)); graph.get(2).add(new Node(4, 3)); graph.get(4).add(new Node(2, 3)); graph.get(2).add(new Node(3, 3)); graph.get(3).add(new Node(2, 3)); graph.get(4).add(new Node(3, 1)); graph.get(3).add(new Node(4, 1)); // Source node src = 1; // Destination node dest = 3; dijkstra(); } // Function to implement Dijkstra's algorithm public static void dijkstra() { // array to keep track of unvisited nodes boolean[] done = new boolean[n + 1]; // node array to keep track of path // from source to all other nodes Node[] table = new Node[n + 1]; // initialise all nodes for (int i = 1; i <= n; i++) table[i] = new Node(-1, Integer.MAX_VALUE); // source to source length is 0 table[src].length = 0; // Dijkstra's algorithm implementation for (int count = 1; count <= n; count++) { int min = Integer.MAX_VALUE; int minNode = -1; // find the minimum length node // from unvisited nodes for (int i = 1; i <= n; i++) { if (!done[i] && table[i].length < min) { min = table[i].length; minNode = i; } } // visit the minNode done[minNode] = true; // iterator to traverse all connected // nodes to minNode ListIterator iter = graph.get(minNode).listIterator(); while (iter.hasNext()) { Node nd = (Node)iter.next(); int v = nd.label; int w = nd.length; // update the distance from minNode // of unvisited nodes if (!done[v] && table[minNode].length + w < table[v].length) { table[v].length = table[minNode].length + w; table[v].label = minNode; } } } // length is now available from source to all nodes System.out.println("Wire from " + dest + " to " + src + " with length " + table[dest].length); int next = table[dest].label; System.out.print("Path is : " + dest + " "); // path from destination to source via all // intermediate nodes with minimum length while (next >= 0) { System.out.print(next + " "); next = table[next].label; } System.out.println(); }} |
Wire from 3 to 1 with length 4 Path is : 3 4 5 1
Time Complexity: Time Complexity for the above implementation of Dijkstra’s algorithm is O(n^2).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
