Algorithm-and-Data-Structure/AlgorithmCode/ShortestPath/DijkstraAlgorithm.java at master · lemidia/Algorithm-and-Data-Structure · 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
packageShortestPath;

importjava.io.*;
importjava.util.*;

publicclassDijkstraAlgorithm{
staticintn, m;
staticintdist[];
staticintcheck[];
staticIntegerprev[];
staticArrayList<Edge> adjecentGraph[];

staticvoiddijkstra(ints, inte){ // Single Source Shortest Path (SSSP)
// Import priority queue : Insert O(log n)
PriorityQueue<Edge> priorityQueue = newPriorityQueue<>(newComparator<Edge>() {
@Override
publicintcompare(Edgeo1, Edgeo2) {
returnInteger.compare(o1.cost, o2.cost); // Non decreasing order of each node cost
 }
 });

Arrays.fill(dist, Integer.MAX_VALUE); // Init all the destination
dist[s] = 0; // Init that start is 0
priorityQueue.offer(newEdge(s, 0));
while (!priorityQueue.isEmpty()){
Edget = priorityQueue.poll();
intcur = t.to;
intcurCost = t.cost;
// If minCost in the priority queue is greater than
// current cost then skip.
// This means that stale outdated node is skipped
if (dist[cur] < curCost) continue;
check[cur] = 1; // Visited cur node
for (Edgenx : adjecentGraph[cur]){
if (check[nx.to] == 1) // if nx node has been visited
continue;
intnewDist = curCost + nx.cost;
if (dist[nx.to] > newDist){ // If newDist is less than dist of cur's next dist
dist[nx.to] = newDist; // Edge relaxation
priorityQueue.offer(newEdge(nx.to, newDist)); // Insert relaxed edge
//prev[nx.to] = cur; //Path
 }
 }
if (cur == e)
return;
 }
 }


publicstaticvoidmain(String[] args) throwsIOException {
BufferedReaderbr = newBufferedReader(newInputStreamReader(System.in));
StringBuildersb = newStringBuilder();
StringTokenizerst;

n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
dist = newint[n+1];
check = newint[n+1];
prev = newInteger[n+1];
adjecentGraph = newArrayList[n+1];
// Init Graph
for (inti = 0; i < n+1; i++)
adjecentGraph[i] = newArrayList<>();

for (inti = 0; i < m; i++) {
st = newStringTokenizer(br.readLine());
adjecentGraph[Integer.parseInt(st.nextToken())].add(newEdge(
Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())
 ));
 }

st = newStringTokenizer(br.readLine());
ints = Integer.parseInt(st.nextToken());
inte = Integer.parseInt(st.nextToken());

dijkstra(s, e); // Operate Dijkstra Algorithm
System.out.print(dist[e]);

/* Path Print
 System.out.println();
 for (Integer i = e; i != null ; i = prev[i]) {
 sb.append(i).append(">-"); // i.e 1 -> 2 -> 3 ... 5
 }
 System.out.print(sb.reverse().delete(0, 2));
 */
 }
staticclassEdge{ // Edge information
intto, cost;

publicEdge(intto, intcost) {
this.to = to;
this.cost = cost;
 }
 }
}