dijkstra algorithm

Monitoring Water Distribution Networks (WDNs) often involves pressure metering, but determining the optimal placement of pressure sensors and accurately calculating the average pressure remains a challenge. To address this, it is crucial to measure pressure at the Average Zone Point (AZP) in the field. However, conventional methods for AZP determination can introduce significant errors. This paper introduces a novel method for AZP determination in WDNs. The approach transforms the existing WDN into a graph and assigns edge weights based on pipe energy loss. By employing Dijkstra's algorithm and a new cost function, the optimal AZP location is identified. This method was applied to two reference networks, Hanoi and modified Poulakis, yielding promising results. Pressure measurements obtained through this method more accurately represent the network's average pressure, with an absolute error of less than 0.5% for the studied networks. Moreover, this approach significantly reduces errors compared to conventional methods, achieving an error reduction of over 93%. This innovative method holds great potential for adoption by water and wastewater companies.

Optimal routing is one of the most widely used network issues in transportation planning and aims to find the shortest route among the available routes. Shortest Path Problem Focuses on finding the path with the least distance, time, or cost from source node to destination node. On the other hand, this processing time is very important in applications related to intelligent and user-based transportation. Various deterministic and innovative algorithms are used to perform routing. One of these algorithms is the ant colloquial ant colony optimization algorithm, which is inspired by the ant feeding behavior of ants and deals with the issue of routing from nest to feed, and in the present article, its results with two other algorithms, namely genetics. And Dijkstra is compared. Genetic algorithm is a meta-heuristic algorithm and Dijkstra is a definite algorithm. All three algorithms were tested on three small networks with 200 nodes, medium with 1000 nodes and large with 2000 nodes. Examination of the results showed that the ant colony algorithm gives better results in large networks. The computational time of the ant colony algorithm algorithm is close to the computational time of the genetic algorithm, but it is more accurate and its computational accuracy is the same as the Diextra definitive algorithm method.

In the event of a crisis, appropriate decisions for helping the crisis regions play an important role in reducing life and financial loss. This paper aimed at using the Geographic Information Systems (GIS) to optimize relief to critical regions that are required specified resources by vehicles on road networks of the country. To meet this goal, network analysis including optimum path finding and optimal resource allocation are needed. The optimum path between rescue stations and critical regions is achieved by taking the travel time as the weight of road. Moreover, the optimal resource allocation is obtained by introducing a proposed objective function with minimizing time and cost criteria. Both data management and presenting of the results are accomplished by the GIS. As a prototype system, the proposed approach is implemented and assessed in Yazd province.

Finding the shortest path from origin point to destination point is of vital importance in different cases. In a network, the length of arcs could show the length of the path, time of the path, or any other parameter. A fuzzy shortest path has a variety of applications. Now suppose that there are arcs with no specified length, or with specified length that vary depending on other parameters such as traffic, accidents etc. Moreover, on certain occasions such as smuggling, security forces may doubt the weight of arcs. In such cases, the use of fuzzy shortest path would not be efficient. The Intuitionistic fuzzy set theory can be considered as a generalization of fuzzy set theory in which non-membership function is used in addition to membership function, independently. Note that in fuzzy theory, no difference is considered between presence of data or reasons in favor or against any given subject. In other words, if membership function of an element be half from the fuzzy set, we cannot infer that information was little or that negative and positive reasons were provided with the same amount. Whereas the Intuitionistic fuzzy set and logic is capable of overcoming a number of the limitations of the fuzzy algorithm theory such as supporting doubts and uncertainty. On the other hand, due to the fact that one of the present issues in the graph is finding the shortest path in terms of uncertainty and lack of adequate information of distances. In this paper, the shortest path of Dijkstra algorithm is expanded for the graph with Intuitionistic fuzzy arcs having incomplete data. In this article, two problems with corresponding solutions are presented. The first challenge is about combining the arcs solved by using triangular Intuitionistic fuzzy numbers. The second problem concerns the method of comparing the arcs. To compare the arcs, there are numerous ways including utilizing centroid, maximum and minimum sets, integral values etc. Finally, integral values method was implemented. The reason for using this method is capability to differ between state of decision-maker like optimism and pessimism. So one can change equal inputs accordance to different condition to give different outputs. In this regards, we provide a numerical example of a road network. This network includes 25 nodes and 46 arcs. It is assumed that the value of arcs is triangular Intuitionistic fuzzy numbers as noted above. Then, the algorithm was tested on the network and was compared with the conventional fuzzy method. Finally, the result of algorithm has been compared with the figures and tables and presented difference of the fuzzy and intuitionistic fuzzy paths. It should also be noted that in the case of information lack and algebraic uncertainties abound, Intuitionistic fuzzy logic will be useful, bearing more appropriate results compared to cases done with fuzzy logic. That is because the use of this algorithm allows us to analyse the possible routes pessimistically, cautiously, optimistically and moderately. Hence, information and lack of information as well as doubts and uncertainty will also be taken into account. As a result, the use of this algorithm provides results that are more adaptable to the given condition to be implemented by the decision maker.

Facilitation of transportation is one of the most important applications of Geographic Information System (GIS). In this area the network capabilities of GIS such as shortest path computation,could be very useful. Different criteria have ever considered for shortest path analysis in GIS such as: Distance, travel time, path comfort, path beauty. Travel time criterion has some random continues variations, due to its relation to traffic. Therefore, path finding based on these criterions by current algorithms such as Dijkstra is not suitable. In this field a development of algorithms that can be used on dynamic networks is necessary. In this paper we have developed an algorithm for this purpose that used statistical information of travel time in previous days for prediction of travel time in future. Also for modeling of the randomness of traffic, we have used a risk parameter for each edge in network. We have used the model of space-time partitioning for consideration of observed travel time, predicted travel time and risk parameters together. Finally for testing the developed algorithm, a case study has been explained in this paper. The implemented case study showed the usefulness of represented method in finding shortest path beside current static methods where the total travel time between two points in tested network was reduced from 35.71 minutes by static methods to 29.43 minutes. Certainly, the usefulness of our represented method could be more apparent by increased distance between origin and destination in the network.