FilesExpand file tree

 master

/

FloydWarshall.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

73 lines (68 loc) · 3.39 KB

 master

/

FloydWarshall.java

Copy path

Top

File metadata and controls

• Code
• Blame

73 lines (68 loc) · 3.39 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

package DataStructures.Graphs;

import java.util.Arrays;

import java.util.Scanner;

public class FloydWarshall {

private int DistanceMatrix[][];

private int numberofvertices;//number of vertices in the graph

public static final int INFINITY = 999;

public FloydWarshall(int numberofvertices) {

DistanceMatrix = new int[numberofvertices + 1][numberofvertices + 1];//stores the value of distance from all the possible path form the source vertex to destination vertex

Arrays.fill(DistanceMatrix, 0);

this.numberofvertices = numberofvertices;

}

public void floydwarshall(int AdjacencyMatrix[][])//calculates all the distances from source to destination vertex

{

for (int source = 1; source <= numberofvertices; source++) {

for (int destination = 1; destination <= numberofvertices; destination++) {

DistanceMatrix[source][destination] = AdjacencyMatrix[source][destination];

}

}

for (int intermediate = 1; intermediate <= numberofvertices; intermediate++) {

for (int source = 1; source <= numberofvertices; source++) {

for (int destination = 1; destination <= numberofvertices; destination++) {

if (DistanceMatrix[source][intermediate] + DistanceMatrix[intermediate][destination]

< DistanceMatrix[source][destination])

// if the new distance calculated is less then the earlier shortest

// calculated distance it get replaced as new shortest distance

{

DistanceMatrix[source][destination] = DistanceMatrix[source][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[source][destination] + "\t");

}

System.out.println();

}

}

public static void main(String... arg) {

Scanner scan = new Scanner(System.in);

System.out.println("Enter the number of vertices");

int numberOfVertices = scan.nextInt();

int[][] adjacencyMatrix = 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++) {

adjacencyMatrix[source][destination] = scan.nextInt();

if (source == destination) {

adjacencyMatrix[source][destination] = 0;

continue;

}

if (adjacencyMatrix[source][destination] == 0) {

adjacencyMatrix[source][destination] = INFINITY;

}

}

}

System.out.println("The Transitive Closure of the Graph");

FloydWarshall floydwarshall = new FloydWarshall(numberOfVertices);

floydwarshall.floydwarshall(adjacencyMatrix);

scan.close();

}

}