forked from IamBisrutPyne/Java-Programs
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFloydWarshall.java
More file actions
78 lines (65 loc) · 2.22 KB
/
FloydWarshall.java
File metadata and controls
78 lines (65 loc) · 2.22 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
* Program: Floyd-Warshall Algorithm
* Description:
* The Floyd-Warshall algorithm is a dynamic programming approach used to find
* the shortest paths between all pairs of vertices in a weighted graph.
*
* It can handle positive and negative edge weights (but not negative cycles).
*
* Example:
* Input: 4 vertices, adjacency matrix with edge weights
* Output: Shortest path matrix showing minimum distances between every pair
*
* Author: Joyston Monteiro
* Contribution: Hacktoberfest 2025
*/
import java.util.*;
public class FloydWarshall {
// Define infinity as a large value
static final int INF = (int) 1e9;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of vertices: ");
int n = sc.nextInt();
int[][] graph = new int[n][n];
System.out.println("Enter adjacency matrix (use 99999 for no edge):");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = sc.nextInt();
}
}
floydWarshall(graph, n);
sc.close();
}
// Core algorithm
public static void floydWarshall(int[][] graph, int n) {
int[][] dist = new int[n][n];
// Initialize distance matrix
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = graph[i][j];
// Dynamic Programming logic
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist, n);
}
// Display the result
public static void printSolution(int[][] dist, int n) {
System.out.println("\nShortest distances between every pair of vertices:");
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist[i][j] == INF)
System.out.print("INF ");
else
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}
}