Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
mat_path_example.cc
Go to the documentation of this file.
1
27#include <iostream>
28#include <tpl_graph.H>
29#include <tpl_dynArray.H>
30
31using namespace std;
32using namespace Aleph;
33
34int main()
35{
36 cout << "=== Path Reconstruction from Matrices: Educational Examples ===\n\n";
37
38 // =========================================================================
39 // EXAMPLE 1: Understanding Distance vs Path Matrices
40 // =========================================================================
41 {
42 cout << "--- Example 1: Distance Matrix vs Path Matrix ---\n\n";
43
44 cout << "SCENARIO: Simple road network\n";
45 cout << "=============================\n\n";
46
47 cout << "Cities: A(0), B(1), C(2), D(3)\n\n";
48
49 cout << "Direct roads:\n";
50 cout << " A -> B: 10 miles\n";
51 cout << " A -> C: 5 miles\n";
52 cout << " C -> B: 2 miles\n";
53 cout << " C -> D: 8 miles\n";
54 cout << " B -> D: 4 miles\n\n";
55
56 const int INF = 9999;
57 const int N = 4;
58
59 // Initial distance matrix (direct connections only)
60 int dist[N][N] = {
61 {0, 10, 5, INF}, // A
62 {INF, 0, INF, 4}, // B
63 {INF, 2, 0, 8}, // C
64 {INF, INF, INF, 0} // D
65 };
66
67 cout << "Initial Distance Matrix (direct connections):\n";
68 cout << " A B C D\n";
69 for (int i = 0; i < N; ++i)
70 {
71 char names[] = {'A', 'B', 'C', 'D'};
72 cout << " " << names[i] << " ";
73 for (int j = 0; j < N; ++j)
74 {
75 if (dist[i][j] == INF)
76 cout << " INF ";
77 else
78 cout << " " << dist[i][j] << " ";
79 }
80 cout << "\n";
81 }
82
83 cout << "\nAFTER FLOYD-WARSHALL:\n\n";
84
85 cout << "Final Distance Matrix (shortest paths):\n";
86 cout << " A -> D: 11 miles (via C then B)\n";
87 cout << " Direct would be INF, but A->C->B->D = 5+2+4 = 11\n\n";
88
89 cout << "PATH MATRIX stores intermediate nodes:\n";
90 cout << " path[A][D] = C (go through C first)\n";
91 cout << " path[C][D] = B (then go through B)\n";
92 cout << " path[B][D] = -1 (direct connection)\n\n";
93
94 cout << "KEY INSIGHT: Distance tells HOW FAR, path matrix tells WHICH WAY\n\n";
95 }
96
97 // =========================================================================
98 // EXAMPLE 2: Reconstructing a Path
99 // =========================================================================
100 {
101 cout << "--- Example 2: Step-by-Step Path Reconstruction ---\n\n";
102
103 cout << "GOAL: Find path from A to D\n";
104 cout << "===========================\n\n";
105
106 // Path matrix (built during Floyd-Warshall)
107 const int N = 4;
108 int path[N][N] = {
109 {-1, -1, -1, 2}, // A: to reach D, go through C first
110 {-1, -1, -1, -1}, // B: direct connections
111 {-1, -1, -1, 1}, // C: to reach D, go through B first
112 {-1, -1, -1, -1} // D: no outgoing paths
113 };
114
115 cout << "Path matrix:\n";
116 cout << " A B C D\n";
117 for (int i = 0; i < N; ++i)
118 {
119 char names[] = {'A', 'B', 'C', 'D'};
120 cout << " " << names[i] << " ";
121 for (int j = 0; j < N; ++j)
122 {
123 if (path[i][j] == -1)
124 cout << " - ";
125 else
126 cout << " " << (char)('A' + path[i][j]) << " ";
127 }
128 cout << "\n";
129 }
130
131 cout << "\nRECONSTRUCTION ALGORITHM:\n";
132 cout << "========================\n\n";
133
134 int src = 0; // A
135 int dst = 3; // D
136
137 cout << "find_path(A, D):\n\n";
138
139 cout << "Step 1: Check path[A][D] = " << (char)('A' + path[src][dst]) << "\n";
140 cout << " Intermediate node is C\n";
141 cout << " Recursively find: A -> C, C -> D\n\n";
142
143 cout << "Step 2: find_path(A, C):\n";
144 cout << " path[A][C] = -1 (direct)\n";
145 cout << " Add edge: A -> C\n\n";
146
147 cout << "Step 3: find_path(C, D):\n";
148 cout << " path[C][D] = B\n";
149 cout << " Intermediate node is B\n";
150 cout << " Recursively find: C -> B, B -> D\n\n";
151
152 cout << "Step 4: find_path(C, B):\n";
153 cout << " path[C][B] = -1 (direct)\n";
154 cout << " Add edge: C -> B\n\n";
155
156 cout << "Step 5: find_path(B, D):\n";
157 cout << " path[B][D] = -1 (direct)\n";
158 cout << " Add edge: B -> D\n\n";
159
160 cout << "FINAL PATH: A -> C -> B -> D\n\n";
161 }
162
163 // =========================================================================
164 // EXAMPLE 3: Complete Working Example
165 // =========================================================================
166 {
167 cout << "--- Example 3: Full Floyd-Warshall with Path Recovery ---\n\n";
168
169 const int N = 5;
170 const int INF = 99999;
171
172 cout << "Network: 5 cities with highways\n\n";
173
174 // Distance matrix
175 int dist[N][N];
176 int path[N][N];
177
178 // Initialize
179 for (int i = 0; i < N; ++i)
180 {
181 for (int j = 0; j < N; ++j)
182 {
183 if (i == j)
184 dist[i][j] = 0;
185 else
186 dist[i][j] = INF;
187 path[i][j] = -1; // No intermediate node initially
188 }
189 }
190
191 // Add edges
192 dist[0][1] = 10; dist[1][0] = 10; // 0 <-> 1
193 dist[0][2] = 5; dist[2][0] = 5; // 0 <-> 2
194 dist[1][3] = 2; dist[3][1] = 2; // 1 <-> 3
195 dist[2][3] = 9; dist[3][2] = 9; // 2 <-> 3
196 dist[2][4] = 3; dist[4][2] = 3; // 2 <-> 4
197 dist[3][4] = 4; dist[4][3] = 4; // 3 <-> 4
198
199 cout << "Initial distances (direct connections):\n";
200 cout << " 0 <-> 1: 10\n";
201 cout << " 0 <-> 2: 5\n";
202 cout << " 1 <-> 3: 2\n";
203 cout << " 2 <-> 3: 9\n";
204 cout << " 2 <-> 4: 3\n";
205 cout << " 3 <-> 4: 4\n\n";
206
207 // Floyd-Warshall with path reconstruction
208 cout << "Running Floyd-Warshall...\n";
209 for (int k = 0; k < N; ++k)
210 {
211 for (int i = 0; i < N; ++i)
212 {
213 for (int j = 0; j < N; ++j)
214 {
215 if (dist[i][k] + dist[k][j] < dist[i][j])
216 {
217 dist[i][j] = dist[i][k] + dist[k][j];
218 path[i][j] = k; // Store intermediate node
219 }
220 }
221 }
222 }
223
224 cout << "Done!\n\n";
225
226 // Show shortest distances
227 cout << "Shortest Distance Matrix:\n";
228 cout << " 0 1 2 3 4\n";
229 for (int i = 0; i < N; ++i)
230 {
231 cout << " " << i << " ";
232 for (int j = 0; j < N; ++j)
233 {
234 if (dist[i][j] == INF)
235 cout << " INF";
236 else
237 cout << " " << dist[i][j] << " ";
238 }
239 cout << "\n";
240 }
241
242 cout << "\nEXAMPLE QUERIES:\n\n";
243
244 // Query 1: 0 to 4
245 cout << "Shortest path from 0 to 4:\n";
246 cout << " Distance: " << dist[0][4] << "\n";
247 cout << " Path: 0 -> 2 -> 4 (via " << path[0][4] << ")\n";
248 cout << " (Direct: 0->2=5, 2->4=3, Total=8)\n\n";
249
250 // Query 2: 0 to 3
251 cout << "Shortest path from 0 to 3:\n";
252 cout << " Distance: " << dist[0][3] << "\n";
253 if (path[0][3] != -1)
254 cout << " Path: 0 -> ... -> 3 (via " << path[0][3] << ")\n";
255 else
256 cout << " Path: Direct 0 -> 3\n";
257 cout << "\n";
258 }
259
260 // =========================================================================
261 // EXAMPLE 4: Practical Application - GPS Routing
262 // =========================================================================
263 {
264 cout << "--- Example 4: GPS Navigation System ---\n\n";
265
266 cout << "REAL-WORLD APPLICATION:\n";
267 cout << "======================\n\n";
268
269 cout << "USER QUERY: 'Navigate from Home to Airport'\n\n";
270
271 cout << "SYSTEM PROCESS:\n";
272 cout << "1. Look up distance matrix: Home -> Airport = 45 min\n";
273 cout << "2. Look up path matrix: Route goes through Downtown\n";
274 cout << "3. Recursively reconstruct:\n";
275 cout << " a. Home -> Downtown: via Highway-1\n";
276 cout << " b. Downtown -> Airport: via Airport Rd\n\n";
277
278 cout << "NAVIGATION INSTRUCTIONS:\n";
279 cout << " 1. Head east on Main St\n";
280 cout << " 2. Turn right onto Highway-1 (10 mi)\n";
281 cout << " 3. Take exit 15 for Downtown (15 mi)\n";
282 cout << " 4. Continue on Airport Rd (20 mi)\n";
283 cout << " 5. Arrive at Airport (45 min total)\n\n";
284
285 cout << "WHY PATH MATRIX IS ESSENTIAL:\n";
286 cout << " ✓ Gives turn-by-turn directions\n";
287 cout << " ✓ Shows intermediate waypoints\n";
288 cout << " ✓ Allows route alternatives\n";
289 cout << " ✓ Enables traffic rerouting\n\n";
290 }
291
292 // =========================================================================
293 // EXAMPLE 5: When No Path Exists
294 // =========================================================================
295 {
296 cout << "--- Example 5: Handling Unreachable Destinations ---\n\n";
297
298 cout << "PROBLEM: What if no path exists?\n";
299 cout << "=================================\n\n";
300
301 cout << "Example: Island A and Island B (no bridge)\n\n";
302
303 const int N = 2;
304 const int INF = 99999;
305
306 int dist[N][N] = {
307 {0, INF},
308 {INF, 0}
309 };
310 (void)dist;
311
312 cout << "Distance matrix:\n";
313 cout << " A B\n";
314 cout << " A 0 INF\n";
315 cout << " B INF 0\n\n";
316
317 cout << "DETECTION:\n";
318 cout << " if (dist[A][B] == INF):\n";
319 cout << " No path exists!\n\n";
320
321 cout << "USER MESSAGE:\n";
322 cout << " 'Cannot reach destination'\n";
323 cout << " 'No route available'\n";
324 cout << " 'Destination unreachable'\n\n";
325
326 cout << "PRACTICAL HANDLING:\n";
327 cout << " * Suggest alternative destinations\n";
328 cout << " * Show nearby accessible locations\n";
329 cout << " * Offer multi-modal transport (ferry, flight)\n\n";
330 }
331
332 cout << "=== SUMMARY: Path Matrix Reconstruction ===\n";
333 cout << "\n1. WHY PATH MATRIX?\n";
334 cout << " Distance matrix: Tells HOW FAR\n";
335 cout << " Path matrix: Tells WHICH WAY\n";
336 cout << " Both needed for practical routing\n";
337 cout << "\n2. HOW IT WORKS:\n";
338 cout << " During Floyd-Warshall:\n";
339 cout << " When improving path i->j through k:\n";
340 cout << " path[i][j] = k (store intermediate node)\n";
341 cout << " After Floyd-Warshall:\n";
342 cout << " Recursively reconstruct using path matrix\n";
343 cout << "\n3. RECONSTRUCTION ALGORITHM:\n";
344 cout << " function find_path(i, j):\n";
345 cout << " if path[i][j] == -1:\n";
346 cout << " return [i, j] // Direct edge\n";
347 cout << " else:\n";
348 cout << " k = path[i][j]\n";
349 cout << " return find_path(i,k) + find_path(k,j)\n";
350 cout << "\n4. COMPLEXITY:\n";
351 cout << " Floyd-Warshall: O(V^3)\n";
352 cout << " Path reconstruction: O(V) per query\n";
353 cout << " Preprocessing once, query many times\n";
354 cout << "\n5. REAL-WORLD APPLICATIONS:\n";
355 cout << " ✓ GPS navigation systems\n";
356 cout << " ✓ Network routing protocols\n";
357 cout << " ✓ Flight planning systems\n";
358 cout << " ✓ Supply chain logistics\n";
359 cout << " ✓ Game pathfinding\n";
360 cout << "\n6. KEY PROPERTIES:\n";
361 cout << " * Works for all pairs simultaneously\n";
362 cout << " * Handles negative weights (not negative cycles)\n";
363 cout << " * Simple recursive implementation\n";
364 cout << " * Space: O(V^2) for path matrix\n";
365 cout << "\n7. BEST PRACTICES:\n";
366 cout << " * Always build path matrix with distance matrix\n";
367 cout << " * Check for INF before reconstructing\n";
368 cout << " * Cache reconstructed paths if queried often\n";
369 cout << " * Handle edge cases (no path, same node)\n";
370
371 return 0;
372}
N
#define N
Definition fib.C:294
main
int main()
Definition mat_path_example.cc:34
Aleph
Main namespace for Aleph-w library functions.
Definition ah-arena.H:89
Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693
std
STL namespace.
tpl_dynArray.H
Lazy and scalable dynamic array implementation.
tpl_graph.H
Generic graph and digraph implementations.