Overview This program compares two shortest-path algorithms: BFS (Breadth-First Search) – finds the shortest route based on fewest hops between intersections. Dijkstra’s Algorithm – finds the shortest total distance using weighted edges. It uses the Xi’an Road Network dataset (Xian.road-d.txt), which includes over 100,000 intersections and 500,000+ roads. The goal is to evaluate which algorithm is faster and more efficient on a large real-world dataset.
How to Run the Program Open the project in CLion (or any C++ IDE). Make sure the dataset file Xian.road-d.txt is located in: DSA-Project2/data/
Build and run the program (Main). The program will load the dataset and print: Load(ms): V: E: Coords: no Valid vertex ID range: [min_ID, max_ID] When prompted, enter the source and target vertex IDs (within the printed range). Example: Enter source vertex ID: 10001 Enter target vertex ID: 10500
The program verifies that both IDs exist, then automatically finds the path between them using: BFS – shortest by hops. Dijkstra – shortest by total distance.
What Happens Internally Step 1: Loads the Xi’an dataset and constructs a graph using an adjacency list. Step 2: Displays the valid range of vertex IDs to guide user input. Step 3: Accepts the user’s start and end intersection IDs. Step 4: Converts external IDs (from the file) into internal indices used by the program. Step 5: Runs: BFS to compute the shortest path in terms of hops. Dijkstra’s Algorithm to compute the shortest physical distance. Step 6: Records: -Total vertices and edges. -Time taken (in milliseconds) by each algorithm. -Total distance (in meters) for each resulting path. -Sample Output Load(ms): 887 V: 123995 E: 563084 Coords: no Valid vertex ID range: [10001, 161234] ===== Results ===== BFS_hops: 257 BFS_dist_m: 54227.45 BFS_time_ms: 73 Dij_hops: 366 Dij_dist_m: 37819.21 Dij_time_ms: 49
Interpreting the Results BFS_hops: Number of intersections visited in the BFS route (fewest turns). BFS_dist_m: Total distance (in meters) of the BFS path. BFS_time_ms: Time BFS took to find the path. Dij_hops: Number of intersections in Dijkstra’s route. Dij_dist_m: Actual shortest path distance in meters. Dij_time_ms: Time Dijkstra’s algorithm took to compute it.
Optional Visual Output If coordinate data is available, an SVG map (out.svg) is generated showing: BFS path in blue. Dijkstra path in red. Start intersection marked green, destination marked purple.
In Summary Input: Source and target intersection IDs from the dataset. Process: Runs and compares BFS (unweighted) and Dijkstra (weighted). Output: Path distance, time taken, and performance comparison. Goal: Identify which algorithm is more effective for shortest-path finding in large, real-world road networks.