AIT — Discrete Mathematics (PCC-203-COM) | CCE-II Case Studies | Roll No: 12
CODE — CASE STUDY 2
JAVA FILE :
1 import [Link].*;
2
3 public class DijkstraRoadNetwork {
4
5 static final int INF = Integer.MAX_VALUE;
6
7 static int[] dijkstra(int[][] graph, int src, int V) {
8 int[] dist = new int[V];
9 boolean[] visited = new boolean[V];
10 [Link](dist, INF); dist[src] = 0;
11
12 PriorityQueue<int[]> pq =
13 new PriorityQueue<>((a, b) -> a[1] - b[1]);
14 [Link](new int[]{src, 0});
15
16 while (![Link]()) {
17 int[] curr = [Link]();
18 int u = curr[0];
19 if (visited[u]) continue; visited[u] = true;
20 for (int v = 0; v < V; v++) {
21 if (!visited[v] && graph[u][v] != 0
22 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
23 dist[v] = dist[u] + graph[u][v];
24 [Link](new int[]{v, dist[v]});
25 }
26 }
27 }
28 return dist;
29 }
30
31 public static void main(String[] args) {
32 String[] cities = {"Pune","Mumbai",
33 "Nashik","Aurangabad","Kolhapur"};
34 int V = [Link];
35
36 // Adjacency matrix — distances in km (0 = no direct road)
37 int[][] graph = {
38 { 0, 149, 212, 0, 228},
39 {149, 0, 167, 0, 0},
40 {212, 167, 0, 157, 0},
41 { 0, 0, 157, 0, 0},
42 {228, 0, 0, 0, 0} };
43
44 int src = 0; // Source: Pune
45 int[] dist = dijkstra(graph, src, V);
46
47 [Link]("%-15s %s%n", "Destination", "Distance(km)");
AIT — Discrete Mathematics (PCC-203-COM) | CCE-II Case Studies | Roll No: 12
48 for (int i = 0; i < V; i++) {
49 [Link]("%-15s %s%n", cities[i],
50 dist[i] == INF ? "Unreachable" : dist[i] + " km");
51 }
52 }
53 }
JAVASCRIPT FILE
1 <!DOCTYPE html>
2 <html lang="en">
3 <head>
4 <meta charset="UTF-8">
5 <title>Road Network — Google Maps + GeoGebra</title>
6 <script src="[Link]
7 <style>
8 body { margin:0; font-family:Arial; background:#f0f4f8; }
9 h2 { text-align:center; color:#1F3864; padding:10px; }
10 #container { display:flex; gap:10px; padding:10px; }
11 #map { width:55%; height:520px;
12 border:2px solid #2E75B6; border-radius:8px; }
13 #ggb-div { height:400px;
14 border:2px solid #2E75B6; border-radius:8px; }
15 .controls { text-align:center; padding:10px; }
16 button { background:#2E75B6; color:#fff; border:none;
17 padding:8px 14px; margin:4px; border-radius:4px; cursor:pointer; }
18 button:hover{ background:#1F3864; }
19 #result { text-align:center; color:#1F3864; font-size:16px;
20 font-weight:bold; padding:8px; }
21 </style>
22 </head>
23 <body>
24 <h2>Road Network Visualization — Graph Theory on Google Maps</h2>
25 <div class="controls">
26 From: <select id="src">
27 <option value="0">Pune</option>
28 <option value="1">Mumbai</option>
29 <option value="2">Nashik</option>
30 </select>
31 To: <select id="dst">
32 <option value="3" selected>Aurangabad</option>
33 <option value="4">Kolhapur</option>
34 </select>
35 <button onclick="findShortestPath()">Find Shortest Path</button>
36 <button onclick="resetMap()">Reset</button>
37 </div>
38 <div id="container">
39 <div id="map"></div>
40 <div id="ggb-div"></div>
AIT — Discrete Mathematics (PCC-203-COM) | CCE-II Case Studies | Roll No: 12
41 </div>
42 <div id="result">Select cities and click Find.</div>
43
44 <script>
45 var cities = [
46 {name:"Pune", lat:18.5204, lng:73.8567},
47 {name:"Mumbai", lat:19.0760, lng:72.8777},
48 {name:"Nashik", lat:19.9975, lng:73.7898},
49 {name:"Aurangabad", lat:19.8762, lng:75.3433},
50 {name:"Kolhapur", lat:16.7050, lng:74.2433} ];
51
52 var edges = [
53 [0,1,149], [0,2,212], [0,4,228],
54 [1,2,167], [2,3,157] ];
55
56 // Dijkstra's shortest path — O((V+E) log V)
57 function dijkstra(src) {
58 var V = [Link];
59 var dist = new Array(V).fill(Infinity);
60 var prev = new Array(V).fill(-1);
61 var vis = new Array(V).fill(false);
62 dist[src] = 0;
63 for (var c = 0; c < V-1; c++) {
64 var u = -1;
65 for (var v = 0; v < V; v++)
66 if (!vis[v] && (u===-1 || dist[v] < dist[u])) u = v;
67 if (dist[u] === Infinity) break;
68 vis[u] = true;
69 [Link](function(e) {
70 var a=e[0], b=e[1], w=e[2];
71 if (a===u && dist[u]+w < dist[b]) { dist[b]=dist[u]+w; prev[b]=u; }
72 else if (b===u && dist[u]+w < dist[a]) { dist[a]=dist[u]+w; prev[a]=u; }
73 });
74 }
75 return {dist,prev};
76 }
77
78 function findShortestPath() {
79 var src = parseInt([Link]("src").value);
80 var dst = parseInt([Link]("dst").value);
81 var result = dijkstra(src);
82 // reconstruct path via predecessor array
83 var path = [], at = dst;
84 for (; at !== -1; at = [Link][at]) [Link](at);
85 [Link]();
86 // highlight MST path red on map
87 [Link](p => [Link](null));
88 polylines = [];
89 [Link](e => {
90 var inPath = [Link]((n,i) =>
AIT — Discrete Mathematics (PCC-203-COM) | CCE-II Case Studies | Roll No: 12
91 i < [Link]-1 && ((path[i]===e[0]&&path[i+1]===e[1])||
92 (path[i]===e[1]&&path[i+1]===e[0])));
93 var line = new [Link]({
94 path: [{lat:cities[e[0]].lat, lng:cities[e[0]].lng},
95 {lat:cities[e[1]].lat, lng:cities[e[1]].lng}],
96 strokeColor: inPath ? "#FF0000" : "#AAAAAA",
97 strokeWeight: inPath ? 5 : 2, map: map
98 });
99 [Link](line);
100 });
101 [Link]("result").innerHTML =
102 "Shortest Path: " + [Link](i => cities[i].name).join(" → ")
103 + "<br>Total Distance: " + [Link][dst] + " km";
104 }
105 </script>
106
107 <!-- Replace YOUR_API_KEY with your Google Maps API key -->
108 <script async defer
109 src="[Link]
110 </script>
111 </body></html>