Java Program to Implement Dijkstra’s Algorithm using Set

This Java program,to Implement Dijkstra’s algorithm using Set.Dijkstra’s algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.

Here is the source code of the Java program to implement Dijkstra’s algorithm using Set. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

import java.util.* use for all util file .we used this library as replace to below  given library.

1. import java.util.HashSet;

2. import java.util.InputMismatchException;

3. import java.util.Iterator;

4. import java.util.Scanner;

5. import java.util.Set;

7. public class DijkstraAlgorithmSet

8. {

9.     private int distances[];

10.     private Set<Integer> settled;

11.     private Set<Integer> unsettled;

12.     private int number_of_nodes;

13.     private int adjacencyMatrix[][];

15.     public DijkstraAlgorithmSet(int number_of_nodes)

16.     {

17.         this.number_of_nodes = number_of_nodes;

18.         distances = new int[number_of_nodes + 1];

19.         settled = new HashSet<Integer>();

20.         unsettled = new HashSet<Integer>();

21.         adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];

22.     }

24.     public void dijkstra_algorithm(int adjacency_matrix[][], int source)

25.     {

26.         int evaluationNode;

27.         for (int i = 1; i <= number_of_nodes; i++)

28.             for (int j = 1; j <= number_of_nodes; j++)

29.                 adjacencyMatrix[i][j] = adjacency_matrix[i][j];

31.         for (int i = 1; i <= number_of_nodes; i++)

32.         {

33.             distances[i] = Integer.MAX_VALUE;

34.         }

36.         unsettled.add(source);

37.         distances[source] = 0;		

38.         while (!unsettled.isEmpty())

39.         {

40.             evaluationNode = getNodeWithMinimumDistanceFromUnsettled();

41.             unsettled.remove(evaluationNode);

42.             settled.add(evaluationNode);

43.             evaluateNeighbours(evaluationNode);

44.         } 

45.     }

47.     private int getNodeWithMinimumDistanceFromUnsettled()

48.     {

49.         int min ;

50.         int node = 0;

52.         Iterator<Integer> iterator = unsettled.iterator();

53.         node = iterator.next();

54.         min = distances[node];

55.         for (int i = 1; i <= distances.length; i++)

56.         {

57.             if (unsettled.contains(i))

58.             {

59.                 if (distances[i] <= min)

60.                 {

61.                     min = distances[i];

62.                     node = i;			

63.                 }

64.             }

65.         }

66.         return node;

67.     }

69.     private void evaluateNeighbours(int evaluationNode)

70.     {

71.         int edgeDistance = -1;

72.         int newDistance = -1;

74.         for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)

75.         {

76.             if (!settled.contains(destinationNode))

77.             {

78.                 if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)

79.                 {

80.                     edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];

81.                     newDistance = distances[evaluationNode] + edgeDistance;

82.                     if (newDistance < distances[destinationNode])

83.                     {

84.                         distances[destinationNode] = newDistance;

85.                     }

86.                     unsettled.add(destinationNode);

87.                 }

88.             }

89.         }

90.     }

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

93.     {

94.         int adjacency_matrix[][];

95.         int number_of_vertices;

96.         int source = 0;

97.         Scanner scan = new Scanner(System.in);

98.         try

99.         {

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

101.             number_of_vertices = scan.nextInt();

102.             adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];

104.             System.out.println("Enter the Weighted Matrix for the graph");

105.             for (int i = 1; i <= number_of_vertices; i++)

106.             {

107.                 for (int j = 1; j <= number_of_vertices; j++)

108.                 {

109.                     adjacency_matrix[i][j] = scan.nextInt();

110.                     if (i == j)

111.                     {

112.                         adjacency_matrix[i][j] = 0;

113.                         continue;

114.                     }

115.                     if (adjacency_matrix[i][j] == 0)

116.                     {

117.                         adjacency_matrix[i][j] =  Integer.MAX_VALUE;

118.                     }

119.                 } 

120.             } 

122.             System.out.println("Enter the source ");

123.             source = scan.nextInt();

125.             DijkstraAlgorithmSet dijkstrasAlgorithm = new DijkstraAlgorithmSet(number_of_vertices);

126.             dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix, source);

128.             System.out.println("The Shorted Path to all nodes are ");

129.             for (int i = 1; i <= dijkstrasAlgorithm.distances.length - 1; i++)

130.             {

131.                 System.out.println(source + " to " + i + " is "+ dijkstrasAlgorithm.distances[i]);

132.             }

133.         } catch (InputMismatchException inputMismatch)

134.         {

135.             System.out.println("Wrong Input Format");

136.         }

137.         scan.close();

138.     }

139. }

Enter the number of vertices
5
Enter the Weighted Matrix for the graph
0 9 6 5 3 
0 0 0 0 0
0 2 0 4 0
0 0 0 0 0
0 0 0 0 0
Enter the source 
1
The Shorted Path to all nodes are 
1 to 1 is 0
1 to 2 is 8
1 to 3 is 6
1 to 4 is 5
1 to 5 is 3