This Java program is to find all pairs shortest path.This program finds the shortest distance between every pair of vertex in the graph.
Here is the source code of the Java program to find all pairs shortest path. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.Scanner; public class AllPairShortestPath { private int distancematrix[][]; private int numberofvertices; public static final int INFINITY = 999; public AllPairShortestPath(int numberofvertices) { distancematrix = new int[numberofvertices + 1][numberofvertices + 1]; this.numberofvertices = numberofvertices; } public void allPairShortestPath(int adjacencymatrix[][]) { for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { distancematrix[destination] = adjacencymatrix[destination]; } } for (int intermediate = 1; intermediate <= numberofvertices; intermediate++) { for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { if (distancematrix[intermediate] + distancematrix[intermediate][destination] < distancematrix[destination]) distancematrix[destination] = distancematrix[intermediate] + distancematrix[intermediate][destination]; } } } for (int source = 1; source <= numberofvertices; source++) System.out.print("\t" + source); System.out.println(); for (int source = 1; source <= numberofvertices; source++) { System.out.print(source + "\t"); for (int destination = 1; destination <= numberofvertices; destination++) { System.out.print(distancematrix[destination] + "\t"); } System.out.println(); } } public static void main(String... arg) { int adjacency_matrix[][]; int numberofvertices; Scanner scan = new Scanner(System.in); System.out.println("Enter the number of vertices"); numberofvertices = scan.nextInt(); adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1]; System.out.println("Enter the Weighted Matrix for the graph"); for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { adjacency_matrix[destination] = scan.nextInt(); if (source == destination) { adjacency_matrix[destination] = 0; continue; } if (adjacency_matrix[destination] == 0) { adjacency_matrix[destination] = INFINITY; } } } System.out.println("The Transitive Closure of the Graph"); AllPairShortestPath allPairShortestPath= new AllPairShortestPath(numberofvertices); allPairShortestPath.allPairShortestPath(adjacency_matrix); scan.close(); } }
$javac AllPairShortestPath.java $java AllPairShortestPath Enter the number of vertices 4 Enter the Weighted Matrix for the graph 0 0 3 0 2 0 0 0 0 7 0 1 6 0 0 0 The Transitive Closure of the Graph 1 2 3 4 1 0 10 3 4 2 2 0 5 6 3 7 7 0 1 4 6 16 9 0
Related posts:
Java Program to Generate Randomized Sequence of Given Range of Numbers
Spring Boot - Admin Client
Receive email using POP3
Java Program to Implement a Binary Search Algorithm for a Specific Search Sequence
Logging in Spring Boot
Java Program to Implement RoleList API
Java Program to Perform Optimal Paranthesization Using Dynamic Programming
Spring Data JPA and Null Parameters
Simple Single Sign-On with Spring Security OAuth2
Java Program to Implement ConcurrentSkipListMap API
Quick Guide to Spring MVC with Velocity
Simultaneous Spring WebClient Calls
Java Program to Implement Control Table
Custom Error Pages with Spring MVC
Spring Security Logout
Call Methods at Runtime Using Java Reflection
Java Program to Implement Sparse Matrix
Introduction to Spring Cloud Netflix – Eureka
Spring’s RequestBody and ResponseBody Annotations
Spring Cloud – Tracing Services with Zipkin
Calling Stored Procedures from Spring Data JPA Repositories
Introduction to Spring Data MongoDB
Abstract class và Interface trong Java
An Introduction to Java.util.Hashtable Class
Toán tử trong java
The Difference Between map() and flatMap()
Java Program to Implement the Hill Cypher
Java Program to Implement Network Flow Problem
Convert a Map to an Array, List or Set in Java
Hướng dẫn sử dụng Java String, StringBuffer và StringBuilder
Java Program to Implement Miller Rabin Primality Test Algorithm
Quản lý bộ nhớ trong Java với Heap Space vs Stack