Repository navigation
Expand file tree
/
Copy pathVipulsAlgorithm.java
More file actions
101 lines (79 loc) · 2.83 KB
/
Copy pathVipulsAlgorithm.java
File metadata and controls
101 lines (79 loc) · 2.83 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
import java.util.*;
class Edge {
int to;
int cost;
int traffic;
int risk;
int safety;
public Edge(int to, int cost, int traffic, int risk, int safety) {
this.to = to;
this.cost = cost;
this.traffic = traffic;
this.risk = risk;
this.safety = safety;
}
}
public class VipulsAlgorithm{
static Map<Integer, List<Edge>> graph = new HashMap<>();
static int destination = 4; // E
static Map<Integer, Score> dp = new HashMap<>();
static class Score {
int totalCost;
int totalTraffic;
int totalRisk;
int totalSafety;
public Score(int cost, int traffic, int risk, int safety) {
this.totalCost = cost;
this.totalTraffic = traffic;
this.totalRisk = risk;
this.totalSafety = safety;
}
// Compare two scores using dominance
public boolean isBetterThan(Score other) {
return (this.totalCost <= other.totalCost &&
this.totalTraffic <= other.totalTraffic &&
this.totalRisk <= other.totalRisk &&
this.totalSafety >= other.totalSafety);
}
@Override
public String toString() {
return "Cost: " + totalCost + ", Traffic: " + totalTraffic +
", Risk: " + totalRisk + ", Safety: " + totalSafety;
}
}
public static Score dfs(int node, Set<Integer> visited) {
if (node == destination) {
return new Score(0,0,0,0); // base case
}
if (dp.containsKey(node)) {
return dp.get(node); // reuse result
}
visited.add(node);
Score best = null;
for (Edge e : graph.getOrDefault(node, new ArrayList<>())) {
if (visited.contains(e.to)) continue; // optional to avoid immediate cycles
Score subScore = dfs(e.to, visited);
if (subScore == null) continue;
Score current = new Score(
subScore.totalCost + e.cost,
subScore.totalTraffic + e.traffic,
subScore.totalRisk + e.risk,
subScore.totalSafety + e.safety
);
if (best == null || current.isBetterThan(best)) {
best = current;
}
}
visited.remove(node);
dp.put(node, best);
return best;
}
public static void main(String[] args) {
graph.put(0, Arrays.asList(new Edge(1,2,3,1,5)));
graph.put(1, Arrays.asList(new Edge(2,3,2,2,4), new Edge(4,4,2,1,5)));
graph.put(2, Arrays.asList(new Edge(3,1,5,3,3)));
graph.put(3, Arrays.asList(new Edge(1,1,1,1,2), new Edge(4,2,3,2,4)));
Score result = dfs(0, new HashSet<>());
System.out.println("Best Path Score from A to E: " + result);
}
}