-
Notifications
You must be signed in to change notification settings - Fork 0
/
ShortestPathInDag.java
52 lines (43 loc) · 1.6 KB
/
ShortestPathInDag.java
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
package graph;
import java.util.List;
public class ShortestPathInDag {
private final WeightedGraph graph;
public ShortestPathInDag(WeightedGraph graph) {
this.graph = graph;
}
public int[] shortestPath(int source) {
int[] distance = new int[graph.getVerticesCount()];
for (int i = 0; i < graph.getVerticesCount(); i++) {
distance[i] = Integer.MAX_VALUE;
}
distance[source] = 0;
List<Integer> sortedGraph = graph.bfs();
for (int vertex: sortedGraph) {
for (Edge e : graph.adjacent(vertex)) {
if (distance[e.getSource()] != Integer.MAX_VALUE) {
if (distance[e.getDestination()] > distance[e.getSource()] + e.getWeight()) {
distance[e.getDestination()] = distance[e.getSource()] + e.getWeight();
}
}
}
}
return distance;
}
public static void main(String args[]) {
WeightedGraph g = new DirectedWeightedGraph(4);
g.addEdge(0, 1, 1);
g.addEdge(1, 3, 2);
g.addEdge(1, 2, 3);
g.addEdge(2, 3, 4);
System.out.print(g);
System.out.println("Bfs :" + g.bfs());
ShortestPathInDag path = new ShortestPathInDag(g);
int[] distance = path.shortestPath(1);
System.out.println();
System.out.println("Shortest Path");
for (int i = 0; i < g.getVerticesCount(); i++) {
String val = distance[i] != Integer.MAX_VALUE ? String.valueOf(distance[i]) : "INF";
System.out.println(i + ": " + val);
}
}
}