FilesExpand file tree

 master

/

BFAlgo.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

88 lines (70 loc) · 1.89 KB

 master

/

BFAlgo.java

Top

File metadata and controls

• Code
• Blame

88 lines (70 loc) · 1.89 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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();

}

}

}