Smart Route Finder

A full-stack web application that implements Dijkstra's Algorithm to find the shortest path between locations on a graph. Built with React, Node.js, Express, and MongoDB.

Features

• Graph Data Structure: Represent maps using nodes (locations) and edges (roads with distances)
• Dijkstra's Algorithm: Find shortest paths using a Min-Heap priority queue
• RESTful API: Backend endpoints for nodes, edges, and path calculation
• Clean UI: React components for adding locations, roads, and querying routes
• Real-time Results: Display path and total distance instantly

Tech Stack

• Frontend: React.js with CSS
• Backend: Node.js + Express
• Database: MongoDB
• Algorithm: Dijkstra's Algorithm with Min-Heap implementation

Folder Structure

smart-route-finder/
├── backend/
│   ├── models/
│   │   ├── Node.js          # Location model
│   │   └── Edge.js          # Road model
│   ├── routes/
│   │   └── graphRoutes.js   # API endpoints
│   ├── utils/
│   │   └── dijkstra.js      # Dijkstra algorithm implementation
│   ├── server.js            # Express server
│   ├── .env                 # Environment variables
│   └── package.json
├── frontend/
│   ├── public/
│   │   └── index.html       # React entry point
│   ├── src/
│   │   ├── components/
│   │   │   ├── AddNode.js      # Add location component
│   │   │   ├── AddEdge.js      # Add road component
│   │   │   └── FindPath.js     # Find path component
│   │   ├── api.js           # API client
│   │   ├── App.js           # Main app component
│   │   ├── App.css          # Styles
│   │   ├── index.js         # React DOM render
│   │   └── index.html       # HTML template
│   ├── package.json
│   └── node_modules/
└── README.md

Installation & Setup

Prerequisites

• Node.js (v14+)
• MongoDB (installed and running)
• npm or yarn

1. Start MongoDB

mongod --dbpath C:\data\db

2. Start Backend

cd backend
npm install
npm start

Backend runs on http://localhost:5000

3. Start Frontend (in new terminal)

cd frontend
npm install
npm start

Frontend runs on http://localhost:3000

API Endpoints

Nodes (Locations)

• GET /api/nodes - Get all locations
• POST /api/nodes - Add location
  • Body: { "name": "CityA" }

Edges (Roads)

• POST /api/edges - Add road
  • Body: { "source": "nodeId", "destination": "nodeId", "weight": 10 }

Shortest Path

• POST /api/shortest-path - Find shortest route
  • Body: { "sourceId": "nodeId", "destinationId": "nodeId" }
  • Response: { "path": ["A", "B", "C"], "totalDistance": 25 }

Usage

1. Open http://localhost:3000
2. Add Locations: Enter location names
3. Add Roads: Select source/destination and distance
4. Find Route: Select start/end points and click "Find Shortest Path"
5. View the shortest route and total distance

Dijkstra's Algorithm

Implemented with Min-Heap Priority Queue:

1. Initialize all distances to ∞ (except start = 0)
2. Add start node to priority queue
3. Process nodes in order of shortest distance
4. Update neighbor distances if shorter path found
5. Reconstruct path using previous node map
6. Time Complexity: O((V + E) log V)

Sample Data

Create test data:

# Add nodes (get returned IDs)
curl -X POST -H "Content-Type: application/json" -d "{\"name\":\"A\"}" http://localhost:5000/api/nodes
curl -X POST -H "Content-Type: application/json" -d "{\"name\":\"B\"}" http://localhost:5000/api/nodes

# Add edge (use node IDs from above)
curl -X POST -H "Content-Type: application/json" -d "{\"source\":\"<ID_A>\",\"destination\":\"<ID_B>\",\"weight\":10}" http://localhost:5000/api/edges

# Find path
curl -X POST -H "Content-Type: application/json" -d "{\"sourceId\":\"<ID_A>\",\"destinationId\":\"<ID_B>\"}" http://localhost:5000/api/shortest-path

Troubleshooting

Issue	Solution
MongoDB connection error	Ensure mongod is running: mongod --dbpath C:\data\db
React "index.html not found"	Frontend files are now complete and ready to start
CORS errors	Backend has CORS enabled; check both servers running
Port in use	Change PORT in backend .env or stop existing process

License

ISC

Getting Started

Prerequisites

• Node.js (v14 or higher)
• MongoDB (v4 or higher)
• npm (v6 or higher)

Installation

1. Clone the repository:

   git clone <repository-url>
   cd smart-route-finder
   

2. Backend setup:

   cd backend
   npm install
   

3. Frontend setup:

   cd ../frontend
   npm install
   

Environment Variables

Create a .env file in the backend directory with the following content:

MONGODB_URI=mongodb://localhost:27017/smartroutefinder
PORT=5000

Running the Application

1. Start MongoDB (if not running as a service):

   mongod
   

2. Start the backend server:

   cd backend
   npm start
   

   The server will run on http://localhost:5000

3. Start the frontend development server:

   cd frontend
   npm start
   

   The application will run on http://localhost:3000

API Endpoints

• GET /api/nodes - Get all locations
• POST /api/nodes - Add a new location
  • Body: { "name": "Location Name" }
• POST /api/edges - Add a new road
  • Body: { "source": "nodeId", "destination": "nodeId", "weight": 10 }
• POST /api/shortest-path - Find shortest path between two locations
  • Body: { "sourceId": "nodeId", "destinationId": "nodeId" }

Usage

1. Open the application in your browser (http://localhost:3000)
2. Add locations using the "Add Location" form
3. Add roads between locations using the "Add Road" form (specify source, destination, and distance)
4. Select source and destination locations in the "Find Shortest Path" section
5. Click "Find Shortest Path" to see the route and total distance

Sample Data

You can add the following sample data to test the application:

Locations (Nodes):

• A
• B
• C
• D
• E

Roads (Edges):

• A to B: 4
• A to C: 2
• B to C: 1
• B to D: 5
• C to D: 8
• C to E: 10
• D to E: 2

Test Case: Find shortest path from A to E:

• Expected Path: A → C → B → D → E
• Expected Total Distance: 2 + 1 + 5 + 2 = 10

Implementation Details

Dijkstra's Algorithm

The backend implements Dijkstra's Algorithm using a Priority Queue (Min Heap) for efficient extraction of the minimum distance node.

Key aspects:

• Time Complexity: O((V + E) log V) where V is vertices and E is edges
• Space Complexity: O(V)
• The algorithm finds the shortest path in a weighted graph with non-negative weights

Graph Representation

The graph is stored in MongoDB with two collections:

• Nodes: Stores location information (id, name)
• Edges: Stores road information (source, destination, weight)

When calculating the shortest path, the backend:

1. Retrieves all nodes and edges from the database
2. Builds an adjacency list representation of the graph
3. Applies Dijkstra's Algorithm to find the shortest path
4. Returns the path with location names and total distance

Future Enhancements

• Visual graph display using a library like D3.js or vis.js
• Dynamic weight updates to simulate traffic conditions
• Multiple route alternatives (k-shortest paths)
• User authentication and saved maps
• Mobile-responsive design
• Deployment instructions for production (Heroku, AWS, etc.)

License

This project is open source and available under the MIT License."# Smart-Road-Finder"