Dijkstra Pathfinding Visualizer

An interactive educational tool that visualizes Dijkstra's shortest path algorithm in real-time using Python and Pygame.

Overview

This application provides an intuitive, visual way to understand how Dijkstra's algorithm explores a grid-based environment to find the optimal path between two points. Watch as the algorithm systematically evaluates nodes, navigates around obstacles, and ultimately discovers the shortest route.

Features

Core Functionality

• Interactive Grid System: Click and drag to create custom maze layouts
• Visual Algorithm Execution: Real-time visualization of the pathfinding process
• Customizable Environment: Place start points, end points, and walls anywhere on the grid
• Path Highlighting: Clear visualization of the discovered shortest path

Visual Indicators

• 🟠 Orange: Start node
• 🔵 Turquoise: End/Target node
• ⬛ Black: Walls/Obstacles
• 🟢 Green: Open nodes (being explored)
• 🔴 Red: Closed nodes (already evaluated)
• 🟣 Purple: Final shortest path

User Controls

• Set Start: Define the starting position for pathfinding
• Set End: Define the destination point
• Draw Walls: Create obstacles to navigate around
• Run Dijkstra: Execute the pathfinding algorithm with visualization
• Reset: Clear the entire grid and start fresh
• Right-Click: Remove any placed element (walls, start, or end nodes)

Installation

Prerequisites

• Python 3.7 or higher
• pip (Python package installer)

Setup Instructions

1. Clone or download this repository

   git clone https://github.com/harshil2424/Dijkstra-pathfinding-algo.git
   cd Dijkstra-pathfinding-algo

2. Install required dependencies

   pip install pygame

3. Run the application

   python main.py

Usage Guide

Basic Workflow

1. Launch the application - Run python main.py
2. Place the start node - Click "Set Start" button, then click on any grid cell
3. Place the end node - Click "Set End" button, then click on another grid cell
4. Draw obstacles - Click "Draw Walls" button, then click and drag across cells to create barriers
5. Run the algorithm - Click "Run Dijkstra" or press SPACEBAR to start visualization
6. Reset if needed - Click "Reset" or press C to clear the grid

Controls

Mouse Controls

Action	Control
Place start/end/walls	Left Click
Remove items	Right Click
Drag to draw walls	Click + Drag

Keyboard Shortcuts

Key	Action
SPACEBAR	Run Dijkstra's algorithm
C	Clear/Reset the grid

How It Works

Dijkstra's Algorithm

Dijkstra's algorithm is a graph search algorithm that finds the shortest path between nodes in a graph. This implementation uses:

1. Priority Queue: Explores nodes in order of their distance from the start
2. Distance Tracking: Maintains the shortest known distance to each node
3. Backtracking: Reconstructs the path once the target is reached

Visualization Process

1. Green nodes: Represent the "frontier" - nodes currently being considered
2. Red nodes: Show explored territory - nodes already evaluated
3. Purple path: The final shortest path from start to finish

Project Structure

Dijkstra-pathfinding-algo/
│
├── main.py              # Main application file
├── README.md            # Project documentation
└── requirements.txt     # Python dependencies

Technical Details

Grid System

• Grid-based pathfinding on a 2D plane
• Configurable grid size and cell dimensions
• Supports obstacle placement for complex pathfinding scenarios

Algorithm Implementation

• Efficient priority queue implementation for node selection
• Distance calculation using grid-based coordinates
• Path reconstruction using parent node tracking

Educational Value

This visualizer is perfect for:

• Computer Science Students: Understanding graph algorithms visually
• Algorithm Enthusiasts: Exploring pathfinding behavior with different obstacle configurations
• Teachers: Demonstrating shortest path algorithms in an engaging way
• Developers: Learning algorithm implementation and visualization techniques

Requirements

pygame>=2.0.0

Future Enhancements

Potential improvements for future versions:

• Additional pathfinding algorithms (A*, BFS, DFS)
• Diagonal movement options
• Variable terrain costs/weights
• Save/Load maze configurations
• Speed control for visualization
• Step-by-step mode
• Performance metrics display

Screenshots

Add screenshots of your application here to showcase:

---

Note: This is an educational tool designed to help visualize and understand pathfinding algorithms. It is not optimized for production pathfinding systems.