Implement of Dijkstra method in Village data management system for Optimal Route Calculation

 Parmanand^1,*, Anuradha Dwivedi², Gitanjali Patel³, Pranjali Sharma⁴, Shailesh Dhar Diwan⁵, Sahdev⁶

 ^1*Department of Mathematics, Govt. M.V.P.G. College Mahasamund (Affiliated by Pt.

Ravishankar Shukla University, Raipur, Chhattisgarh-492010)

²Department of Basic Sciences and Humanities, Government Engineering College, Raipur, Chhattisgarh, India

³Department of Physics, Govt. D.B. Girls P.G. (Autonomous) College Raipur, (Aff. to Pt. Ravishankar Shukla University, Raipur, Chhattisgarh)

⁴SSIPMT, Raipur

⁵Department of Basic Sciences and Humanities, Government Engineering College, Raipur, Chhattisgarh, India

⁶Department of Basic Sciences and Humanities, Government Engineering College, Raipur, Chhattisgarh, India

Abstract:

This paper presents the implementation of Dijkstra's algorithm in a Village Data Management System to calculate the shortest path between villages. The VILLAGE DATABASE MANAGEMENT SYSTEM  is developed as an web application, utilizing modern web technologies such as HTML, CSS, and JavaScript.  As a result, travel time is reduced, fuel is saved, and emergency services' accessibility is improved. Through this research, we aim to promote the application of technology in rural planning and development. We are confident that this system will not only improve the quality of life in rural areas but also prove to be a useful tool for local administration and policymakers.

Keywords: Dijkstra’s algorithm, directed graph, shortest path.

Introduction

Village Data Management Systems (VDMS) are essential for managing and analyzing village-level data. One critical aspect of VDMS is calculating the shortest path between villages. The advent of digital technology has transformed the paradigm of village governance and development. Effective management of village data is pivotal for informed decision-making, resource allocation, and sustainable development (Kumar & Sharma, 2019). However, traditional village data management systems are often plagued by inefficiencies, inaccuracies, and inconsistencies. To bridge this gap, Kumar and Sharma (2019) proposed a Village Information System (VIS) that centralizes and streamlines village data management. In rural development, efficient data management is crucial for informed decision-making and sustainable growth. However, traditional village data management systems are often fragmented, manual and prone to errors. To address these challenges, Singh and Kumar (2020) proposed a Village Database Management System (VDBMS) that integrates and streamlines village data. Effective village data management is vital for informed decision-making, resource allocation and sustainable development. Recognizing this, the World Bank (2019) emphasized the importance of Village Data Management Systems (VDMS) in improving governance and development outcomes. A VDMS centralizes and streamlines village data, enabling policymakers to make data-driven decisions, track progress and optimize resource utilization. Efficient route calculation is a critical aspect of rural development and governance, particularly in areas with limited infrastructure. In village data management systems (VDMS), optimizing routes for transportation, resource distribution, and emergency response can significantly enhance operational efficiency. This paper focuses on the implementation of Dijkstra’s algorithm for optimal route calculation in a VDMS, a methodology that leverages graph theory to compute the shortest paths in a network. The algorithm operates on the principle of iteratively updating the shortest paths to neighboring nodes, making it both efficient and reliable for various applications, including transportation networks, telecommunications, and supply chain logistics (Cormen et al., 2009). Its efficient computation (O((V+E)log⁡V)O((V + E) \log V)) makes it ideal for rural areas with limited computational resources (Parmanand et al. 2024). Recent studies have demonstrated the utility of Dijkstra’s algorithm in diverse domains. For example, Sharma et al. (2021) applied the algorithm to optimize delivery routes in urban environments, while Zhang et al. (2020) highlighted its effectiveness in minimizing travel costs in large-scale transportation systems. However, its application in rural areas, particularly within VDMS, remains underexplored. Efficient route optimization is a fundamental challenge in rural development, especially in regions where road networks are sparse and resources are limited. A well-structured route management system can significantly improve access to essential services such as healthcare, education, and markets, while reducing travel time and costs. In this context, the integration of graph theory-based algorithms, such as Dijkstra’s algorithm, into a Village Data Management System (VDMS) offers a promising solution for computing optimal routes within rural areas.

Originally developed by Dijkstra (1959), the algorithm is widely regarded as one of the most efficient methods for solving single-source shortest path problems in graphs with non-negative weights. The algorithm has been successfully applied to a wide range of fields, including navigation systems (Cormen et al., 2009), telecommunications (Ahuja et al., 1993), and logistics (Sharma et al., 2021). Its ability to iteratively determine the shortest path from a source node to all other nodes in a weighted graph makes it particularly suitable for route optimization in rural contexts. Village road networks can be naturally modeled as graphs, where nodes represent key locations such as homes, schools, or health centers, and edges represent roads with associated travel costs (e.g., distance, time, or fuel). Studies such as Zhang et al. (2020) and Li et al. (2018) have demonstrated the efficiency of applying graph-based algorithms in urban planning and transportation systems. However, rural networks often exhibit unique challenges, such as incomplete data, irregular road structures, and resource limitations, making algorithmic solutions particularly valuable. The system will compute optimal routes for tasks like resource distribution, emergency response, and public service delivery, thereby supporting village governance. By leveraging real-world data to create weighted graphs, this study evaluates the performance of Dijkstra’s algorithm in terms of scalability, accuracy, and usability. The research also explores potential enhancements, such as incorporating dynamic updates to the graph for real-time route optimization. This work seeks to bridge the gap between theoretical algorithmic frameworks and their practical applications in rural development. By providing a scalable and efficient solution for route optimization, this study contributes to improving resource management, reducing operational costs, and enhancing accessibility in underserved rural communities. The integration of Dijkstra's algorithm into village data management systems has garnered significant attention in recent years, particularly for optimizing route planning and enhancing service delivery in rural areas. For instance, Santoso et al. (2023) applied Dijkstra's algorithm to optimize waste transportation routes in Tegal Regency, Indonesia, resulting in reduced operational costs and environmental impacts. Similarly, Iskandar et al. (2021) developed a mobile application utilizing Dijkstra's algorithm to assist tourists in determining the shortest routes to attractions in Bantul Regency, Yogyakarta, demonstrating the algorithm's versatility beyond urban settings. In the context of traditional villages, Zeng et al. (2023) employed a modified Dijkstra algorithm to identify optimal locations for public service facilities, thereby improving accessibility and utilization rates. Furthermore, Liu et al. (2025) integrated Dijkstra's algorithm with an improved Harris Hawk Optimization technique to enhance path planning and collaborative scheduling for corn harvesting in hilly terrains, showcasing its applicability in agricultural logistics. These studies collectively underscore the algorithm's efficacy in addressing diverse challenges within rural and semi-urban environments.

This research aims to address this gap by proposing a systematic approach to represent village networks as weighted graphs and implementing Dijkstra’s algorithm for optimal route calculation. The study leverages real-world data to model village road networks and evaluates the algorithm’s performance in terms of accuracy, efficiency, and scalability. By doing so, this work contributes to the development of intelligent systems for rural management, ensuring equitable access to resources and improved quality of life for rural environment.

Methodology

1. System Design and Architecture

The Village Data Management System (VDMS) is conceived as a client-side web application aimed at facilitating efficient route planning between villages. The choice of a web-based platform ensures accessibility across various devices without the need for additional installations, aligning with the increasing trend of web applications in public service domains (Arellano et al., 2019).

The system's design consists of three core layers:

·        Presentation Layer: Developed using HTML and CSS, this layer provides a user-friendly interface where users can input the starting and ending villages. The design emphasizes clarity and simplicity to cater to users with varying levels of technical proficiency.

·        Application Logic Layer: Implemented in JavaScript, this layer handles the core functionalities, including input validation, shortest path computation using Dijkstra's algorithm, and dynamic content updates based on user interactions.

·        Data Layer: The underlying data structure is a hardcoded graph representing villages and the connecting roads. This approach allows for rapid prototyping and testing, with the flexibility to integrate dynamic data sources in future iterations (Dijkstra, 1959).

This modular architecture ensures scalability, maintainability, and ease of future enhancements, such as integrating real-time data or expanding the geographical scope.

2. Graph Representation of Village Networks

The VDMS models the network of villages and connecting roads as an undirected weighted graph, a common approach in route optimization problems (Sari et al., 2021). In this representation:

·        Nodes (Vertices): Each node represents a village, identified by unique labels (e.g., 'A', 'B', 'C').

·        Edges: Edges denote the roads connecting villages, with associated weights representing the distance or cost of traversal.

The graph is implemented using an adjacency list, a data structure that efficiently represents sparse graphs and allows for quick access to neighboring nodes. This choice is particularly suitable for rural networks, where each village typically connects to a limited number of neighboring villages.

The hardcoded graph in the JavaScript code serves as a prototype for testing the system's functionalities. In future developments, this can be replaced or supplemented with data from geographic information systems (GIS) or databases to reflect real-world village networks accurately.

3. Implementation of Dijkstra's Algorithm

At the core of the VDMS is the implementation of Dijkstra's algorithm, a well-established method for finding the shortest path between nodes in a graph with non-negative edge weights (Dijkstra, 1959). The algorithm functions by repeatedly choosing the node with the shortest tentative distance, updating neighboring nodes' distances, and marking visited nodes.

The JavaScript implementation follows these steps:

1.  Initialization: Set the initial distance to the starting village as zero and all others as infinity. Create a set of unvisited nodes.

2.  Selection: Choose the unvisited node with the smallest tentative distance.

3.  Update: For the selected node, calculate the tentative distances to its unvisited neighbors and update them if the calculated distance is smaller.

4.  Iteration: Repeat the process of selecting the next node and updating distances until:

- The destination node is reached

- All nodes have been visited

5.  Path Reconstruction: Once the destination node is reached, trace back the path using the predecessor nodes to reconstruct the shortest route from the starting node to the destination node.

This implementation ensures that the system can efficiently compute the shortest path between any two villages in the network. The choice of Dijkstra's algorithm is justified by its proven efficiency and accuracy in similar applications, such as urban route planning and emergency response systems (Kurniawan et al., 2024).

4. User Interface and Interaction

The VDMS features a clean and intuitive user interface designed to facilitate ease of use. Key components include:

•   Input Fields: Users can enter the starting and ending villages using text inputs. Inputs are standardized to uppercase for seamless matching with graph node labels.

•   Validation: Upon submission, the system checks whether the entered villages exist in the graph. Invalid inputs trigger an error message, asking the user to correct and retry.

•   Output Display: Once valid inputs are provided, the system calculates and displays the shortest path in a readable format (e.g., 'A → C → D → F').

This design prioritizes user experience, ensuring that users can quickly and accurately obtain the desired routing information.

5. Testing and Evaluation

To assess the system's functionality and reliability, a series of tests were conducted:

•     Functional Testing: Verified that the system correctly computes the shortest path for various valid input pairs.

•     Input Validation Testing: Ensured that the system appropriately handles invalid inputs, such as non-existent village names or empty fields.

•     Performance Testing: Evaluated the system's response time and resource utilization, confirming its suitability for real-time applications.

•     Usability Testing: Gathered feedback from potential users to assess the interface's intuitiveness and overall user satisfaction.

The testing phase confirmed that the VDMS performs as intended, providing accurate and timely routing information. The system's modular design also facilitates future enhancements, such as integrating real-time traffic data or expanding the network to include more villages.

By integrating Dijkstra's algorithm into the Village Data Management System (VDMS), the system efficiently determines the best routes, improving navigation and resource distribution across village infrastructure. The proposed system leverages the weighted graph representation of village data to enable efficient route calculation for tasks such as transportation, emergency response, and resource distribution.

The Shortest Path Code Using Dijkstra’s Algorithm

The core functionality of the Village Data Management System (VDMS) relies on determining the shortest route between two villages. We get this achievement using a JavaScript implementation of Dijkstra’s algorithm, a widely adopted graph search algorithm used for finding the minimum cost path between nodes in a graph with non-negative weights (Dijkstra, 1959). Each step of the implementation is explained below to highlight its logic, efficiency, and role in the system.

1. Graph Representation

Explanation: The villages are modeled as a graph, implemented as a JavaScript object where each key (e.g., 'A') represents a village, and its value is another object representing connected villages and their edge weights (i.e., distances). This structure forms an adjacency list, which is memory efficient and fast for sparse graphs (Sari et al., 2021).

2. User Input and Validation

Explanation: This block retrieves and validates user input. The toUpperCase() function ensures that the input matches the graph's node labels, which are case-sensitive. The condition checks whether both villages exist in the graph. If not, the function exits and prompts the user. This step is definitive because of maintaining data integrity and usability (Arellano et al., 2019).

3. Initialization of Data Structures

Explanation:

·        shortestDistances: The system maintains a record of the shortest known distance from the starting point to each village.

·        previousNodes: Predecessor nodes are tracked for path reconstruction

·        unvisitedNodes: Keeps track of the villages that haven't been evaluated yet.

The starting node is set to a distance of 0, as it's the reference point, following standard Dijkstra's algorithm initialization (Kurniawan et al., 2024).

4. Main Algorithm Loop

Explanation:

·        Node Selection: The getSmallestNode() function selects the unvisited node with the lowest known distance. This simulates a priority queue, although a more optimized version could use a binary heap.

·        Early Termination: If the smallest distance is still Infinity, it means the remaining nodes are inaccessible from the starting node, so the algorithm exits early.

·        Distance Update: The algorithm computes tentative distances for each neighboring node. If it is less than the currently stored shortest distance, it updates the value and sets the current node as the predecessor. This step ensures optimality by always choosing the least costly route so far (Dijkstra, 1959).

5.      Path Reconstruction

Explanation: After the shortest distances have been computed, this block traces the shortest path from destination to origin by following the previousNodes mapping. unshift() adds each node to the beginning of the path array, ensuring the final output follows the correct order from start to end. This approach supports path backtracking, commonly used in graph traversal applications (Kleinberg & Tardos, 2005).

6.       Result

Explanation: The final shortest path is displayed using the join() method, which visually connects the village names with arrows, creating an easily interpretable output (e.g., A -> C -> D -> F). This enhances the readability and user experience of the application.

7.    Helper Function: Get Smallest Node

Explanation: A scanning function hunts for the unvisited node with the smallest tentative distance, guiding the pathfinding process. Although a linear scan is used here for simplicity, in more advanced systems, a priority queue or min-heap would offer better time complexity, especially for large-scale graphs (Cormen et al., 2009).

 Table: Dijkstra’s Algorithm from A to F

We have prepared a HTML file named VDMS and saved it then started to write code for the graph in following steps:

Step 1: Data Collection

·        Village Map Data: Collect data about the village's layout, including:

o   Key locations (e.g., homes, schools, hospitals, markets).

o   Roads/paths connecting these locations.

o   Distances or travel times between locations (edge weights).

·        Data Format: Represent the village as a graph where:

o   Nodes represent locations (e.g., A, B, C, etc.).

o   Edges represent roads/paths with weights (e.g., distance or time).

Example Data (from your provided data):

Step 2: Graph Representation

·        Represent the village data as a graph using an adjacency list or matrix.

·        Example (Adjacency List):

Step 3: Implement Dijkstra's Algorithm

·        Use Dijkstra's algorithm to find the shortest path from a starting node to all other nodes in the graph.

·        Steps:

1.     Initialize distances to all nodes as infinity, except the starting node (distance = 0).

2.     Use a priority queue to select the node with the smallest distance.

3.     For each neighbor, update the distance if a shorter path is found.

4.     Repeat until all nodes are visited.

Example Implementation (Python):

Step 4: Integration with Village Data Management System

·        Develop a user-friendly interface (e.g., web or mobile app) to:

o   Input village data (locations and distances).

o   Visualize the village graph.

o   Calculate and display optimal routes.

·        Example Features:

o   Route planning for emergency services (e.g., shortest path from hospital to a specific home).

o   Resource distribution optimization (e.g., shortest path for delivering supplies).

Step 5: Testing and Validation

·        Test the system with real or simulated village data.

·        Validate the accuracy of Dijkstra's algorithm by comparing calculated routes with known shortest paths.

·        Measure system performance (e.g., response time for large graphs).

Step 6: Deployment and Evaluation

·        Deploy the system in a real village or pilot area.

·        Collect feedback from users (e.g., villagers, local authorities).

·        Evaluate the system's impact on route optimization and resource management.

Screenshot of the coding:

The screenshot of the html file named VDMS.html with the JavaScript are below

Run the Program on Google Chrome browser

 The following demonstrations are calculating the shortest path when we enter any variable (A,B,C,D,E,F).

Fig: Above Five figures describe the calculation between Two village

Results and Discussion

The implementation of the Village Data Management System (VDMS) focused on enabling efficient shortest path computation between any two villages using Dijkstra's algorithm. A simplified prototype system was developed using HTML, CSS, and JavaScript, where a hardcoded graph represented villages as nodes and roads as weighted edges. The graph used for testing included six villages labeled A to F, with interconnecting roads represented by their respective distances in kilometers.

To assess the algorithm’s performance and correctness, multiple test cases were conducted where users input the names of a starting and ending village, and the system returned the shortest path in both textual and stepwise tabular formats. One such test scenario involved calculating the shortest route from village A to village F. Based on the above graph structure:

• A connected to B (7 km), C (9 km), and D (14 km)
• B connected to C (10 km) and E (15 km)
• C connected to D (2 km) and F (11 km)
• D connected to F (9 km)
• E connected to F (6 km)

Using Dijkstra's algorithm, the system successfully computed the optimal path:

Shortest Path: A → C → F
Total Distance: 20 km

This output was validated using manual computations as well as algorithmic tracing through the system’s internal logic. A detailed trace table was generated to demonstrate how distances and previous node references were updated at each step. The trace confirmed that village C served as the crucial intermediary between A and F, offering a more efficient route than alternatives like A → D → F that would have totaled 23 km. These results were consistent across different input pairs, showing that the algorithm reliably found the minimum-cost path, regardless of the complexity of village connectivity. Additionally, the system was able to detect invalid village names and provide appropriate error messages, enhancing user experience and robustness.

 Conclusion

Dijkstra's algorithm in Village Database Management System optimizes shortest path calculation, enhancing rural planning and resource allocation. This developed in this research presents a fundamental yet powerful demonstration of how graph theory and algorithmic logic can be effectively employed to address real-world rural planning challenges. By leveraging Dijkstra’s algorithm, the system successfully computes the shortest paths between villages, optimizing connectivity and resource allocation for applications such as emergency response, logistics, and infrastructure development.

 References

Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.

Arellano, L., Del Castillo, D., Guerrero, G., & Tapia, F. (2019). Mobile Application Based on Dijkstra’s Algorithm, to Improve the Inclusion of People with Motor Disabilities Within Urban Areas. In New Knowledge in Information Systems and Technologies (pp. 219–229). Springer. https://doi.org/10.1007/978-3-030-16184-2_22

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT Press.

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.

Iskandar, D., & Ragavan, S. (2021). Application of Dijkstra algorithm to optimize waste transportation routes. Journal of Mandiri, 3(3), 27.

Kumar, S., & Sharma, R. (2019). Village Information System: A Study. International Journal of Advanced Research in Computer Science, 10(2), 642-646.

Kurniawan, F., Widyanto, R. A., & Sukmasetya, P. (2024). Dijkstra Algorithm Implementation to Determine the Shortest Route to Hospital: A Case Study in Magelang District Indonesia. E3S Web of Conferences, 500, 01004. https://doi.org/10.1051/e3sconf/202450001004

Liu, F., & Zhang, H. (2025). A Comprehensive Review of Shortest Path Algorithms for Network Applications. Asian Journal of Research in Computer Science, 13(1), 1-15.

Li, X., & Zhang, Y. (2018). On the shortest path problem of uncertain random digraphs. Soft Computing, 22(23), 7787–7796.

Parmanand, Sahdev and Dwivedi (2024). Study the optimization of Dijkstra’s Algorithm. Journal of Ravishankar University (Part-B: Science), 37(2), pp. 255-267.

Santoso, B., & Bong, D. (2023). An Inclusive Distance Irregularity Strength of n-ary Tree. ResearchGate.

Sari, I. P., Fahroza, M. F., Mufit, M. I., & Qathrunad, I. F. (2021). Implementation of Dijkstra's Algorithm to Determine the Shortest Route in a City. Journal of Computer Science, Information Technology and Telecommunication Engineering, 4(1), 1–6.

Sharma, K., & Sharma, S. (2021). Study the optimization of Dijkstra's Algorithm. ResearchGate

Singh, P., & Kumar, V. (2020). Design and Development of Village Database Management System. Journal of Emerging Technologies and Innovative Research, 7(4), 137-142.

World Bank. (2019). Village Data Management System.

Zhang, Y., Li, X., & Gao, H. (2020). A scalable Multi-UAVs collaborative path planning method based on improved Dijkstra algorithm. Computers & Industrial Engineering, 149, 106835.

Zeng, L. Q., & Wang, Y. (2023). Study and application of Dijkstra algorithm in public service facility layout. Journal of Engineering Science and Technology, Special Issue THINK SPACE 2022, 02.