This is a java program to find the optimized wire length between any two components in an electric circuits. This problem is similar to the problem of finding the shortest path between any two cities in the state. A simple Dijkstra’s algorithm would result in providing the shortest wire length between any two components in electric circuits.
Here is the source code of the Java Program to Optimize Wire Length in Electrical Circuit. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a sample program to find the minimum wire length between two component in a electrical circuits import java.util.*; class Node { public int label; // this node's label (parent node in path tree) public int weight; // weight of edge to this node (distance to start) public Node(int v, int w) { label = v; weight = w; } } public class ShortestPath { public static Scanner in; // for standard input public static int n, m; // n = #vertices, m = #edges public static LinkedList[] graph; // adjacency list representation public static int start, end; // start and end points for shortest path public static void main(String[] args) { in = new Scanner(System.in); // Input the graph: System.out .println("Enter the number of components and wires in a circuit:"); n = in.nextInt(); m = in.nextInt(); // Initialize adjacency list structure to empty lists: graph = new LinkedList[n]; for (int i = 0; i < n; i++) graph[i] = new LinkedList(); // Add each edge twice, once for each endpoint: System.out .println("Mention the wire between components and its length:"); for (int i = 0; i < m; i++) { int v1 = in.nextInt(); int v2 = in.nextInt(); int w = in.nextInt(); graph[v1].add(new Node(v2, w)); graph[v2].add(new Node(v1, w)); } // Input starting and ending vertices: System.out .println("Enter the start and end for which length is to be minimized: "); start = in.nextInt(); end = in.nextInt(); // FOR DEBUGGING ONLY: displayGraph(); // Print shortest path from start to end: shortest(); } public static void shortest() { boolean[] done = new boolean[n]; Node[] table = new Node[n]; for (int i = 0; i < n; i++) table[i] = new Node(-1, Integer.MAX_VALUE); table[start].weight = 0; for (int count = 0; count < n; count++) { int min = Integer.MAX_VALUE; int minNode = -1; for (int i = 0; i < n; i++) if (!done[i] && table[i].weight < min) { min = table[i].weight; minNode = i; } done[minNode] = true; ListIterator iter = graph[minNode].listIterator(); while (iter.hasNext()) { Node nd = (Node) iter.next(); int v = nd.label; int w = nd.weight; if (!done[v] && table[minNode].weight + w < table[v].weight) { table[v].weight = table[minNode].weight + w; table[v].label = minNode; } } } for (int i = 0; i < n; i++) { if (table[i].weight < Integer.MAX_VALUE) { System.out.print("Wire from " + i + " to " + start + " with length " + table[i].weight + ": "); int next = table[i].label; while (next >= 0) { System.out.print(next + " "); next = table[next].label; } System.out.println(); } else System.out.println("No wire from " + i + " to " + start); } } public static void displayGraph() { for (int i = 0; i < n; i++) { System.out.print(i + ": "); ListIterator nbrs = graph[i].listIterator(0); while (nbrs.hasNext()) { Node nd = (Node) nbrs.next(); System.out.print(nd.label + "(" + nd.weight + ") "); } System.out.println(); } } }
Output:
$ javac ShortestPath.java $ java ShortestPath Enter the number of components and wires in a circuit: 4 3 Mention the wire between components and its length: 0 1 2 1 3 3 1 2 2 Enter the start and end for which length is to be minimized: 0 1 0: 1(2) 1: 0(2) 3(3) 2(2) 2: 1(2) 3: 1(3) Wire from 0 to 0 with length 0: Wire from 1 to 0 with length 2: 0 Wire from 2 to 0 with length 4: 1 0 Wire from 3 to 0 with length 5: 1 0
Related posts:
Spring Boot - Code Structure
Giới thiệu Google Guice – Injection, Scope
Hướng dẫn Java Design Pattern – Template Method
Mockito and JUnit 5 – Using ExtendWith
Spring Cloud – Securing Services
Hướng dẫn kết nối cơ sở dữ liệu với Java JDBC
Generating Random Numbers in a Range in Java
Java Program to implement Circular Buffer
Java Program to subtract two large numbers using Linked Lists
Java Program to Implement Min Heap
New Features in Java 12
Java Program to Implement RenderingHints API
Java Program to Solve any Linear Equations
Java Program to Perform Insertion in a BST
Hashing a Password in Java
New Features in Java 8
Java Program to Emulate N Dice Roller
Java Program to Implement the Alexander Bogomolny’s UnOrdered Permutation Algorithm for Elements Fro...
Introduction to Using Thymeleaf in Spring
A Guide to Concurrent Queues in Java
Converting Java Date to OffsetDateTime
Guide to java.util.concurrent.Future
Adding Shutdown Hooks for JVM Applications
Hướng dẫn Java Design Pattern – Facade
Giới thiệu java.io.tmpdir
Find the Registered Spring Security Filters
Creating a Web Application with Spring 5
Intersection of Two Lists in Java
Using a List of Values in a JdbcTemplate IN Clause
The Spring @Controller and @RestController Annotations
Java Program to Implement Stack
Configure a RestTemplate with RestTemplateBuilder