This is a java program find a path between two nodes in a graph if it exists. Path exists between two nodes if there is a connectivity between them through other nodes. A simple run of Breadth First Search will decide whether there is path between two given nodes or not.
Here is the source code of the Java Program to Find Path Between Two Nodes in a Graph. 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:
Refactoring Design Pattern với tính năng mới trong Java 8
Spring Cloud AWS – Messaging Support
Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm
Java Program to Find the Vertex Connectivity of a Graph
Làm thế nào tạo instance của một class mà không gọi từ khóa new?
Java Program to Implement Self Balancing Binary Search Tree
Batch Processing with Spring Cloud Data Flow
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
Java CyclicBarrier vs CountDownLatch
Rest Web service: Filter và Interceptor với Jersey 2.x (P1)
Truyền giá trị và tham chiếu trong java
Custom JUnit 4 Test Runners
Spring Data MongoDB – Indexes, Annotations and Converters
Java Program to Implement Leftist Heap
Spring Cloud AWS – RDS
Java Program to Implement IdentityHashMap API
The Basics of Java Security
Java Program to Implement the Monoalphabetic Cypher
ETL with Spring Cloud Data Flow
Uploading MultipartFile with Spring RestTemplate
Java Program to Implement Shell Sort
OAuth2 Remember Me with Refresh Token
Java Program to Implement Gauss Seidel Method
Java Program to Implement Fermat Factorization Algorithm
Java Program to Implement Shoelace Algorithm
How to Read a File in Java
Converting Between an Array and a Set in Java
Add Multiple Items to an Java ArrayList
A Guide to LinkedHashMap in Java
Migrating from JUnit 4 to JUnit 5
Converting a Stack Trace to a String in Java
Spring Data MongoDB Transactions