-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
167 lines (130 loc) · 4.54 KB
/
index.html
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Dijkstra's Algorithm Tables</title>
<style>
table {
border-collapse: collapse;
width: 40%;
margin: 20px;
}
table, th, td {
border: 1px solid black;
}
th, td {
padding: 10px;
text-align: center;
}
textarea {
margin: 10px;
width: 80%;
height: 100px;
}
input[type="text"] {
margin: 10px;
}
</style>
</head>
<body>
<h2>Dijkstra's Algorithm Tables</h2>
<label for="graphInput">Enter Graph Data:</label>
<textarea id="graphInput" placeholder="source destination weight 1 2 1 1 3 4 2 3 2 2 4 5 3 4 1"></textarea>
<br>
<label for="startNode">Enter Starting Node:</label>
<input type="text" id="startNode" placeholder="Enter starting node" value="1">
<label for="isDirected">Directed Graph:</label>
<input type="checkbox" id="isDirected" checked>
<button onclick="updateGraph()">Update Graph</button>
<table id="distanceTable">
<!-- The table for distances will be generated dynamically using JavaScript -->
</table>
<table id="predecessorTable">
<!-- The table for predecessors will be generated dynamically using JavaScript -->
</table>
<script>
let graph = {};
function updateGraph() {
const inputText = document.getElementById('graphInput').value;
const startNode = document.getElementById('startNode').value;
const isDirected = document.getElementById('isDirected').checked;
// Reset the graph
graph = {};
// Parse the input and update the graph
const lines = inputText.split('\n');
lines.forEach(line => {
const [start, end, weight] = line.split(' ').map(Number);
if (!graph[start]) graph[start] = {};
if (!graph[end]) graph[end] = {};
graph[start][end] = weight;
if (!isDirected) {
// If the graph is not directed, add the reverse edge
graph[end][start] = weight;
}
});
// Display the updated tables
displayTables(startNode);
}
function dijkstra(graph, start) {
const dist = {};
const predecessor = {};
const visited = {};
const distanceTable = [];
const predecessorTable = [];
const Q = new Set();
// Initialization according to the pseudocode
for (const vertex in graph) {
dist[vertex] = vertex === start ? 0 : Infinity;
predecessor[vertex] = vertex === start ? start : null;
visited[vertex] = false;
Q.add(vertex);
}
while (Q.size > 0) {
let v = null;
// Find the vertex in Q with the minimum dist value
Q.forEach(node => {
if (v === null || dist[node] < dist[v]) {
v = node;
}
});
Q.delete(v);
for (const u in graph[v]) {
const alt = dist[v] + graph[v][u];
if (alt < dist[u]) {
dist[u] = alt;
predecessor[u] = v;
}
}
// Build the distance table row for this step
const distanceRow = Object.keys(graph).map(node => `<td>${dist[node] === Infinity ? '∞' : dist[node]}</td>`);
distanceTable.push(`<tr><td>${v}</td>${distanceRow.join('')}</tr>`);
// Build the predecessor table row for this step
const predecessorRow = Object.keys(graph).map(node => `<td>${predecessor[node] === null ? '-' : predecessor[node]}</td>`);
predecessorTable.push(`<tr><td>${v}</td>${predecessorRow.join('')}</tr>`);
}
return { distanceTable, predecessorTable };
}
// Display the tables
function displayTables(startNode) {
startNode = startNode || Object.keys(graph)[0]; // Use the first node as the start if not provided
const { distanceTable, predecessorTable } = dijkstra(graph, startNode);
const distanceTableElement = document.getElementById('distanceTable');
distanceTableElement.innerHTML = `<tr><th>Step</th>${Object.keys(graph).map(node => `<th>Dist(${node})</th>`).join('')}</tr>${distanceTable.join('')}`;
const predecessorTableElement = document.getElementById('predecessorTable');
predecessorTableElement.innerHTML = `<tr><th>Step</th>${Object.keys(graph).map(node => `<th>Pred(${node})</th>`).join('')}</tr>${predecessorTable.join('')}`;
}
// Initial display
displayTables();
// Listen for Ctrl + Enter to trigger the updateGraph function
document.addEventListener('keydown', function (event) {
if (event.ctrlKey && event.key === 'Enter') {
updateGraph();
}
});
</script>
<br>
<p>Similar tools:</p>
<a href="cpm.html">Find critical path</a>
</body>
</html>