forked from PrajaktaSathe/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDijkstra.java
More file actions
103 lines (87 loc) · 2.6 KB
/
Dijkstra.java
File metadata and controls
103 lines (87 loc) · 2.6 KB
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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Dijkstra {
public static void main(String... args) {
int v = 9;
Graph g = new Graph(v);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
// g.printGraph();
dijkstra(g, 0);
}
private static void dijkstra(Graph g, int src) {
int V = g.v;
int dist[] = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++) {
int u = minDist(dist, visited);
visited[u] = true;
List<AdjNode> list = g.adjList.get(u);
for (AdjNode v : list) {
if (!visited[v.dest] && dist[u] + v.cost < dist[v.dest]) {
dist[v.dest] = dist[u] + v.cost;
}
}
}
System.out.println("Vertex Distance from Source");
for (int i = 0; i < dist.length; i++)
System.out.println(i + " " + dist[i]);
}
private static int minDist(int dist[], boolean[] visited) {
int min = Integer.MAX_VALUE, min_index = -1;
for (int i = 0; i < dist.length; i++) {
if (!visited[i] && dist[i] <= min) {
min = dist[i];
min_index = i;
}
}
return min_index;
}
}
class Graph {
int v;
List<ArrayList<AdjNode>> adjList;
Graph(int v) {
this.v = v;
adjList = new ArrayList<>();
for (int i = 0; i < this.v; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int u, int v, int cost) {
this.adjList.get(u).add(new AdjNode(u, v, cost));
this.adjList.get(v).add(new AdjNode(v, u, cost));
}
public void printGraph() {
for (int i = 0; i < this.v; i++) {
System.out.print(i + " -> ");
for (int j = 0; j < adjList.get(i).size(); j++) {
System.out.print(adjList.get(i).get(j).dest + " ");
}
System.out.println();
}
}
}
class AdjNode {
int source, dest, cost;
AdjNode(int source, int dest, int cost) {
this.source = source;
this.dest = dest;
this.cost = cost;
}
}