-
Notifications
You must be signed in to change notification settings - Fork 7
/
BFAlgo.java
88 lines (70 loc) · 1.89 KB
/
BFAlgo.java
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
79
80
81
82
83
84
85
86
87
88
//Write a program to find the shortest path between vertices using bellman-ford algorithm.
import java.util.*;
import java.io.*;
import java.math.*;
class BFAlgo
{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
//Input the number of nodes in the graph
System.out.println("Enter the number of nodes: ");
int n=s.nextInt();
//Input source and destination node numbers
System.out.println("Enter Source node number :");
int source=s.nextInt();
System.out.println("Enter Destination node number :");
int dest=s.nextInt();
//create distance array
int[] dist=new int[n];
for(int i=0;i<n;i++)
//Initialize the array with a maximum value which is assumed to be far greater then any edge weight
dist[i]=999;
//create adj matrix
int[][] adj_mat=new int[n][n];
System.out.println("Enter adj matrix :");
//Input the adj_matrix
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
adj_mat[i][j]=s.nextInt();
}
}
//display adj_mat
System.out.println("\n\nEntered ADJ MATRIX IS:");
disp(adj_mat);
dist[source]=0;
//loop through all the nodes
for(int k=0;k<n-1;k++)
{
for(int i=0;i<n;i++)
{
//for each node as the souce update the cost in adj_matrix
for(int j=0;j<n;j++)
{
//if there is a direct path between nodes i and j
if(adj_mat[j][i]!=999)
{
//then check if the direct path is shorter than an alternate path through another node
//choose the shortest dist and update the distance array
if(dist[i]>dist[j]+adj_mat[j][i])
dist[i]= dist[j]+adj_mat[j][i];
}
}
}
}
//display statements
for(int i=0;i<n;i++)
System.out.println(source+"-->"+i+" = "+dist[i]);
}
//helper function for 2D matrix
public static void disp(int arr[][])
{
for(int[] x : arr)
{ for(int y : x)
System.out.print(y);
System.out.println();
}
}
}