Graph/DijkstraAlgorithm_ShortestPathInUndirectedGraph.java at main · adv11/Graph · GitHub

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
packageGraph;
importjava.util.*;

/**
 * Input :
 * Adjacency List :
 * 1 -> (2, 2), (4, 1)
 * 2 -> (1, 2), (5, 5), (3, 4)
 * 3 -> (2, 4), (4, 3), (5, 1)
 * 4 -> (1, 1), (3, 3)
 * 5 -> (2, 5), (3, 1)
 * Output :
 * Distance array is:
 * Minimum distance of node 1 from source node 1 is : 0
 * Minimum distance of node 2 from source node 1 is : 2
 * Minimum distance of node 3 from source node 1 is : 4
 * Minimum distance of node 4 from source node 1 is : 1
 * Minimum distance of node 5 from source node 1 is : 5
 */
classPair2implementsComparator<Pair2>{
intnode;
intedgeWeight;

publicPair2(intnode, intedgeWeight) { // user defined constructor
this.node = node;
this.edgeWeight = edgeWeight;
 }

publicPair2() { // default constructor

 }

publicintcompare(Pair2p1, Pair2p2) { // compare method for comparing edge weights of two pairs
// if (p1.edgeWeight < p2.edgeWeight) {
// return -1;
// }
// if (p1.edgeWeight > p2.edgeWeight) {
// return 1;
// }
// return 0;

returnInteger.compare(p1.edgeWeight, p2.edgeWeight);
 }
}

publicclassDijkstraAlgorithm_ShortestPathInUndirectedGraph {
publicstaticvoidmain(String[] args) {
Scannersc = newScanner(System.in);
ArrayList<ArrayList<Pair2>> adjacencyList = newArrayList<>();

// Taking input for number of nodes
System.out.println("Enter the number of nodes:");
intnumberOfNodes = sc.nextInt();

// initializing adjacencyList with new ArrayList<>()
for (inti = 1; i <= numberOfNodes + 1; i++) {
adjacencyList.add(newArrayList<>());
 }

// taking input of adjacent nodes of particular node
for (inti = 1; i <= numberOfNodes; i++) {
System.out.println("Enter number of adjacent nodes to the node : " + i);
intcountOfAdjacentNodes = sc.nextInt();

for (intj = 0; j < countOfAdjacentNodes; j++) {
// node value
System.out.println("Enter node:");
intnode = sc.nextInt();

// edge weight
System.out.println("Enter edge weight:");
intedgeWeight = sc.nextInt();

// adding (node, edge weight) in to the ith index of adjacency list
adjacencyList.get(i).add(newPair2(node, edgeWeight));
 }
 }

int[] distance = newint[numberOfNodes + 1]; // distance array
Arrays.fill(distance, Integer.MAX_VALUE);

System.out.println("Enter the source node:"); // source node
intsourceNode = sc.nextInt();
distance[sourceNode] = 0;

dijkstraAlgorithm(adjacencyList, distance, sourceNode, numberOfNodes); // method calling


// printing the distance array
System.out.println("\n\nDistance array is:");
for (intnode = 1; node <= numberOfNodes; node++) {
System.out.println("Minimum distance of node " + node + " from source node " + sourceNode + " is : " + distance[node]);
 }
 }

publicstaticvoiddijkstraAlgorithm(ArrayList<ArrayList<Pair2>> adjacencyList, int[] distance, intsourceNode, intnumberOfNodes) {
PriorityQueue<Pair2> minPQ = newPriorityQueue<>(numberOfNodes, newPair2()); // min priority queue
minPQ.add(newPair2(sourceNode, 0)); // add new pair(source node, 0)


// while priority queue is not empty
while (!minPQ.isEmpty()) {
Pair2currentPair = minPQ.poll(); // extracting top pair from the priority queue
intcurrentNode = currentPair.node; // this is current node

// exploring adjacent nodes of the current node
for (Pair2adjacentPair : adjacencyList.get(currentNode)) {

/* if it satisfies this condition:
 distance[current node] + edge weight(current node, adjacent node) < distance[adjacent node] then
 add distance[adjacent node] = distance[current node] + edge weight(current node, adjacent node)
 and add new pair into the min priority queue : new pair(adjacent node, distance[adjacent node])
 */
if ((distance[currentNode] + adjacentPair.edgeWeight) < distance[adjacentPair.node]) {
distance[adjacentPair.node] = (distance[currentNode] + adjacentPair.edgeWeight);
minPQ.add(newPair2(adjacentPair.node, distance[adjacentPair.node]));
 }
 }
 }
 }
}