DynamicRouteOptimiser

---

🧮 Algorithm and Data Structures

Component	Role
Adjacency List (Graph)	Represents intersections (nodes) and roads (edges with weights).
Priority Queue (Min-Heap)	Efficiently selects the closest node during pathfinding.
Hash Map – Distance Table	Tracks the shortest distance from the source node.
Hash Map – Parent Table	Records node relationships for path reconstruction.
Dijkstra’s Algorithm	Computes the guaranteed shortest path when all weights are non-negative.

---

🔧 Plan of Implementation

1. Core Logic:

   • Implement Dijkstra’s Algorithm using an adjacency list.

2. Data Representation:

   • Store map data in a JSON file. Example:

     {
       "A": [["B", 4], ["C", 2]],
       "B": [["A", 4], ["D", 5]],
       "C": [["A", 2], ["D", 8]],
       "D": [["B", 5], ["C", 8], ["E", 2]]
     }

3. Backend (Flask):

   • Handles algorithm execution, route calculations, and updates.

4. Frontend (HTML + JS):

   • Allows users to input source/destination.
   • Displays the computed path and distance visually.

---

🔄 How It Works

Step 1: Input

User selects a source and destination via the web interface.

Step 2: Graph Loading

Backend loads the road network from a JSON adjacency list.

Step 3: Path Calculation

Flask backend runs Dijkstra’s Algorithm:

• Initializes all node distances to infinity (∞) except the source = 0.
• Uses a priority queue to explore nearest unvisited nodes.
• Updates neighbor distances if a shorter path is found.
• Records parent nodes for route reconstruction.

Step 4: Output

Returns:

• Shortest path
• Total distance
• Estimated time
• Complexity details

Step 5: Visualization

JavaScript frontend displays the path on a simple map.

Step 6: Dynamic Updates

When traffic data or edge weights change, the system recalculates and re-renders the optimized route.

---

⚖️ Algorithmic Details

Dijkstra’s Algorithm (Min-Heap Implementation)

1. Set initial distance of all nodes to infinity except the source = 0.
2. Use a min-heap to repeatedly extract the node with the smallest tentative distance.
3. For each neighbor, calculate alternative distances.
4. Update distance and parent if shorter.
5. Continue until all nodes are processed or destination is reached.

Time Complexity: O(E log V)
Space Complexity: O(V + E)

---

🧱 Tech Stack

Layer	Technology
Frontend	HTML, CSS, JavaScript
Backend	Python (Flask)
Algorithm	Dijkstra’s Algorithm
Data Storage	JSON Adjacency List
Visualization	JavaScript Map Display

---

🗂️ File Structure