🚇 Delhi Metro Route Finder

A full-stack route optimization application built with a focus on graph algorithms, specifically Dijkstra’s shortest path algorithm, to compute optimal metro routes in Delhi. Users can select source and destination stations and receive:

• 🛤️ Step-by-step route
• 🔁 Interchanges
• ⏱️ Time / 📏 Distance
• 💰 Fare calculation
• 🗺️ Interactive Metro Map
• 📄 Downloadable PDF route

---

💡 Core Objective

This project was built to demonstrate the real-world application of graph data structures and Dijkstra’s algorithm in metro navigation and routing systems.

---

📐 Data Structures Used

• Graph (Adjacency Map): Each station is a node; connections are weighted edges (distance in km or time in seconds).
• Min-Heap: Custom priority queue used for Dijkstra's efficient shortest path computation.
• Dijkstra’s Algorithm: Finds the optimal path from source to destination using a min-cost traversal.
• HashMaps: For storing vertex data and visited tracking.
• Custom Pair structures: For maintaining cost, path-so-far, and time during traversal.

---

🚀 Features

Feature	Description
🔍 Station Autocomplete	Easy-to-search source & destination fields
🧠 Dijkstra Optimization	Fast, accurate path calculation
🧭 Distance / Time Mode	Choose based on preference
🔄 Interchange Detection	Counts and displays interchange points
🧾 Fare Estimator	Based on distance bands
🗺️ Interactive SVG Metro Map	Route path visualized, with a legend
🎨 Responsive UI	React + Tailwind CSS (warm theme)

---

⚙️ Tech Stack

Layer	Tech Used
Frontend	React 18 + TypeScript + Tailwind
State/API	React Query + Axios
Backend	Node.js + Express + TypeScript
Graph Logic	Custom JavaScript Dijkstra Engine

---

🧪 Algorithms in Detail

🔷 Dijkstra’s Algorithm

Implemented as:

• Priority Queue with MinHeap<T> (custom-built)
• Relaxation of neighbors based on edge weights
• Supports both:
  • Distance-based mode (edge weight = distance)
  • Time-based mode (edge weight = 120 + 40 * distance seconds)

📎 Interchange Detection

• Based on station line suffixes (~B, ~Y, etc.)
• Compares line transitions in the route
• Labels interchanges like: Janak Puri~B ==> Dwarka~Y

---

🏁 Getting Started

🔧 Install & Run Locally

# Clone the repo
git clone https://github.com/yourusername/metro-route-finder.git
cd metro-route-finder

# Install backend
cd server
npm install
npm run dev

# In another terminal, start frontend
cd ../client
npm install
npm run dev