COMSATS University Islamabad
CSC-211
Data Structures &
Algorithms
Project
Khazar Khalilov FA22-BSE-053
Muhammad Hassan SP23-BSE-036
To:
Mr. Saif Ullah Ijaz
12th May 2025
Abstract
The Travel Planner System is designed to help users find optimal travel routes based on
cost, time, and distance. By making use of weighted graphs and Dijkstra's algorithm, the
system will provide efficient route planning for various modes of transportation. This
project aims to strengthen core Data Structures and Algorithms (DSA) concepts while
simulating real-world navigation systems. The implementation will use C++ with a focus
on object-oriented programming (OOP) principles.
Introduction
Background
Travel planning is a critical aspect of modern transportation systems, logistics, and
navigation applications. Efficient route optimization can save time, reduce costs, and
improve user experience.
Problem Statement
Current navigation systems often focus on a single metric (e.g., shortest distance or fastest
route). A comprehensive solution that considers multiple factors (cost, time, distance) and
different transportation modes is needed.
Objectives
• Represent cities and routes as weighted graphs.
• Implement Dijkstra's algorithm to find the shortest path.
• Allow dynamic user inputs for start and end points.
• Display all possible routes with associated costs and time.
• Support different transportation modes (e.g., car, bus, train).
Significance
This project addresses a real-world problem while applying core DSA concepts. It
demonstrates the practical use of graphs and algorithms in solving complex problems(i.e
shortest path).
Literature Review
Existing navigation systems like Google Maps and Waze use graph-based algorithms for
route optimization. However, these systems often prioritize one metric over others.
Academic research highlights the importance of multi-criteria decision-making in route
planning, which this project aims to incorporate.
Gaps addressed:
• Integration of multiple optimization criteria (cost, time, distance).
• Customizable transportation modes.
Project Objectives
1. Design a weighted graph to model cities and routes.
2. Implement Dijkstra's algorithm for shortest path calculation.
3. Develop a user-friendly interface for input and output.
4. Ensure scalability for additional features (e.g., traffic updates).
Methodology
Tools and Technologies
• Programming Language: C++
• Version control: Git
• Data Structures: Graphs, Priority Queues
• OOP Principles: Encapsulation & Inheritance
• IDE: VS Code
• No external libraries will be used beyond C++
Implementation Steps
1. Graph Representation:
o Cities as nodes, routes as edges with weights (cost, time, distance).
2. Algorithm:
o Dijkstra's algorithm for pathfinding.
3. User Interaction:
o Console-based input/output (can be extended to GUI).
4. Testing:
o Validate with sample datasets and edge cases.
Project Plan and Timeline
Task Deadline
Proposal Submission 9th May
Graph Implementation 16th May
Algorithm Integration 23rd May
User Interface 30th May
Testing & Debugging 6th June
Final Submission TBD
Budget:
Not applicable, all tools and technologies used are open source.
Expected Outcomes
• A functional Travel Planner System that optimizes routes based on user preferences.
• Demonstration of graph traversal and shortest path algorithms.
• Documentation of design and implementation processes.
Impact & Benefits
• Users: Efficient travel planning with multiple optimization options to generate the
best path for users.
• Students: Hands-on experience with DSA and OOP.
• Academic: Help students relate theoretical DSA concepts with practical problems.
References
[Link]
[Link]
[Link]
[Link]