Finding the Nearest Blood Donors using Dijkstra Algorithm SISFORMA: Journal of Information Systems (e-Journal) Vol.5 | No. 2 |Th. 2018 ISSN 2442-7888 (online) DOI 10.24167/Sisforma.v5i2.1709 40  Finding the Nearest Blood Donors using Dijkstra Algorithm Md. Sabir Hossain sabir.cse@cuet.ac.bd Department of Computer Science and Engineering Chittagong University of Engineering and Technology, Bangladesh Nayan Das nayan27@ieee.org Department of Computer Science and Engineering Chittagong University of Engineering and Technology, Bangladesh Department of Computer Science and Engineering Chittagong University of Engineering and Technology, Bangladesh Md. Al-Hasan al.hasan.baust@gmail.com Department of Computer Science and Engineering Bangladesh Army University of Science and Technology, Bangladesh Abstract— Now-a-days frequent mishaps like the road accident or other life-risking accident leading to operational emergencies are increasing day by day and the blood donor for such victims or patients are very hard to find in a short period. Sometimes it is really tough to collect the blood of the same group from the relatives of a patient in dying moments. The main objective of this work is to make a connection with these two groups who are in need of blood and who are willing to donate. We have determined the shortest distance between blood seeker and blood donors using the Dijkstra Algorithm. Anybody can contact the nearest blood donor of any group in a particular area quickly. By implementing this idea, the harassment of the victim can be lessened and so many lives can be saved. Keywords— Blood donor, Blood Seeker, Dijkstra’s algorithm, Shortest path, Nearest Donor 1. INTRODUCTION According to the Global Health Observatory (GHO) data by WHO, there were 1.25 million road traffic deaths globally in 2013. The number is incessantly increasing with the increasing urbanization. Some of the victims of such mishaps who have plausibility of survival are in need of blood donation and these demands are growing continuously. On the other hand, the number of people interested in blood donation is not so small now-a-days. The main obstacle we face till now is to find the eligible donor nearest to the hospital so that no victim dies in need of blood. The Dijkstra [1-2] is a graph search algorithm to find the shortest distance between nodes with non-negative edges of a graph. Usually, it checks the entire unvisited node from a single source to all other nodes and updates the information if the total distance is smaller than the previous record. Then it marks the particular node as visited. By using the theory of this algorithm, the shortest path can be determined among the donors. That's how the implementation can be done and the problem can be solved. 2. RELATED WORK The application of Dijkstra algorithm is so broad. There are many instances of Muhammad Kamrul Hossain muhammadkamrulhossain@gmail.com Finding the Nearest Blood Donors using Dijkstra Algorithm SISFORMA: Journal of Information Systems (e-Journal) Vol.5 | No. 2 |Th. 2018 ISSN 2442-7888 (online) DOI 10.24167/Sisforma.v5i2.1709 41  implementation based on this algorithm. Some related works based on this algorithm are described below: A. Risald, Antonio E. Mirino and Suyoto [5] In this work, they used Dijkstra and Floyd- Warshall algorithm to find the shortest and closest path to reach a hospital. B. Haijing Wang, Fangfang Zhang and Peng Cui [6] In this project the authors choose this algorithm to choose a parking space by path optimization of a parking lot. They have used the modified Dijkstra algorithm. C. Alican Bozyiğit, Gazihan Alankuş and Efendi Nasiboğlu [7] In this research, they have proposed a modified Dijkstra algorithm which is more efficient for route planning in the public transport network. D. Aram M. Ahmed, Sarkar Hasan Ahmed and Omed Hassan Ahmed [8] Authors have used the algorithm to implement in a project to find the fastest route to all the tourist attraction places and restaurants according to their particular hotel. E. Said Broumi, Mohamed Talea, Assia Bakali and Florentin Smarandache [9] Authors have proposed an extended version of the Dijkstra algorithm to find the shortest path on a network. F. Yong Zhu, Xiaohuan Liu and Xiaohong Yu [10] In this paper, a new method is proposed by the authors to achieve a complete security solution for path optimization. G. Mayur Parulekar, Viraj Padte, Talkien Shah, Kalind Shroff and Rahul Shetty [11] In this work, authors have explored the possibilities to let a car move autonomously. Direct Short-Range Communication Protocol is implemented in this project. H. Yan Zhang and Jun Zhang [12] A robust optimization method is applied to select the hub aerodromes in the airline network and the Dijkstra algorithm is to improve the solution. Similar with this research and project, this algorithm can be used in different sector like composing way selection [13], VLSI routing [14], optimal path planning for aircraft carrier [15] and so on. 3. PROPOSED METHODOLOGY Dijkstra algorithm is the solution of the optimal pathfinding to the single source. Both directed and undirected graph with non- negative weight values is considered for the algorithm. The graphs must be connected to find the optimal result. It will check each unvisited node and update the optimal result. If we consider a country or a city as a graph, for the victim in need of blood, the blood seeker will be the single source and the interested donors of the city will be the nodes. Now we have to find the distances between each of the interested donors from the victim and the minimal distance will be determined and shown as an output. We will also consider the status e.g. active or inactive in online to select the best possible users. We have developed an android application to serve the purpose of our work. The main objective is to find the potential blood donors from a particular place. A user can search by their choice. This project can assist to save a life by managing potential donors effectively. It can considerably reduce the time of finding the donors. 3.1 Flow Chart of the proposed method Outline of the proposed method is described:  At first, the users have to login to our system using their credentials. Finding the Nearest Blood Donors using Dijkstra Algorithm SISFORMA: Journal of Information Systems (e-Journal) Vol.5 | No. 2 |Th. 2018 ISSN 2442-7888 (online) DOI 10.24167/Sisforma.v5i2.1709 42  Figure 01: Flow Chart of Proposed Architecture  The users can be able to know the donor's specified information.  The app will show the quickest result within a short time. The flow diagram is shown in fig. 1. 3.2 Algorithm Used We have calculated shortest distance between the blood seekers and donors using the Dijkstra algorithm. But we have to customize the classical algorithm to fulfill our purpose. We have applied single source all pairs Dijkstra algorithm to find minimum distance from blood seeker [16]. 3.2.1 Algorithm’s Step We have to consider the following assumptions:  Node: The registered user in the system with active GPS  Edge: The relationships between the blood donors and seekers  Starting/Source Node: The blood seeker  Weight: The distance among the users Steps of this algorithm are: 1. Set all donors distance with infinite and the seeker with zero. 2. Update the value of the distance of donor's distance by adding the distance with the weight of that specific donor. 3. Update distance of a donor if the distance of a node is less than the current distance. 4. Repeat steps 2 and 3 until all donor’s distance reach its minimal distance from blood seekers. 5. Match the blood group of the donors with seeker’s group 6. Show the blood donors with minimal distance from blood seeker of matched blood group 3.2.2 Complexity Analysis The whole process needs O(|E|+|V|/log |V|) times [3-4] for the worst case to terminate the operation. 4. IMPLEMENTATION From the app, a user can search the blood donor of any group. If the user wants to be the blood donor then he must have to register first. After completing the registration process a user must go through a login operation. By completing login operation, a user can donate blood in future. The output will be shown on a map which will help the user to find the potential blood donors within a particular area [Fig .04]. Finding the Nearest Blood Donors using Dijkstra Algorithm SISFORMA: Journal of Information Systems (e-Journal) Vol.5 | No. 2 |Th. 2018 ISSN 2442-7888 (online) DOI 10.24167/Sisforma.v5i2.1709 43  Figure 02: Register Figure 03: Login Figure 04: Finding the nearest blood donors The user can contact the blood donors. Thus, the application will help the blood seeker to find out the nearest active blood donors. 5. CONCLUSION Due to lessening the sufferings of people, this project will help them to find the nearest blood donor from a particular area. It makes the procedure easier and faster. Consequently, many seriously wounded people may survive if they are able to find donors timely. By implementing this work, the people will be benefitted and the rate of death can be reduced. Finding a suitable blood donor in the nearest area can be less time consume and will increase the survival rate of the dying patient. We have implemented the fundamental Dijstra algorithm to search the nearest potential donors. We would like to improve this application by adding the opportunity to find out nearest hospitals within a shortest possible time for proper treatment. REFERENCES [1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. RIvest and Clifford Stein, “Introduction to Algorithms”, 1990, page no. 595 [2] Robert Sedgewick and Kevin Wayne, “Algorithms”, Addison-Wesley, 2011, page no. 638 [3] Wikipedia: Aug 5,2017: Available at https://en.wikipedia.org/wiki/Dijkstra%2 7s_algorithm [4] Dijkstra’s shortest path algorithm: Aug 5,2017, Available at www.geeksforgeeks.org/greedy- algorithms-set-6-dijkstras-shortest-path- algorithm/ [5] Risald, Antonio E. Mirino and Suyoto, “Best routes selection using Dijkstra and Floyd-Warshall algorithm”, Information & Communication Technology and System (ICTS), 2017 11th International Conference on 31-31 Oct. 2017. Finding the Nearest Blood Donors using Dijkstra Algorithm SISFORMA: Journal of Information Systems (e-Journal) Vol.5 | No. 2 |Th. 2018 ISSN 2442-7888 (online) DOI 10.24167/Sisforma.v5i2.1709 44  [6] Haijing Wang, Fangfang Zhang and Peng Cui, “A parking lot induction method based on Dijkstra algorithm”, Chinese Automation Congress (CAC), 2017. [7] Alican Bozyiğit, Gazihan Alankuş and Efendi Nasiboğlu, “Public transport route planning: Modified Dijkstra’s algorithm”, Computer Science and Engineering (UBMK), 2017 International Conference on 5-8 Oct. 2017. [8] Aram M. Ahmed, Sarkar Hasan Ahmed and Omed Hassan Ahmed, “Dijkstra algorithm applied: Design and implementation of a framework to find nearest hotels and booking systems in Iraqi”, Current Research in Computer Science and Information Technology (ICCIT), 2017 International Conference on 26-27 April 2017. [9] Said Broumi, Mohamed Talea, Assia Bakali and Florentin Smarandache, “Application of Dijkstra algorithm for solving interval valued neutrosophic shortest path problem”, Computational Intelligence (SSCI), 2016 IEEE Symposium Series on 6-9 Dec. 2016. [10] Yong Zhu, Xiaohuan Liu and Xiaohong Yu, “An optimal path algorithm of high security based on Dijkstra algorithm”, Sensor Network Security Technology and Privacy Communication System (SNS & PCS), 2013 International Conference on 18-19 May 2013. [11] Mayur Parulekar, Viraj Padte, Talkien Shah, Kalind Shroff and Rahul Shetty, “Automatic vehicle navigation using Dijkstra's Algorithm”, Advances in Technology and Engineering (ICATE), 2013 International Conference on 23-25 Jan. 2013. [12] Yan Zhang and Jun Zhang, “Dijkstra's algorithm based robust optimization to airline network planning”, 2010 International Conference on Mechanic Automation and Control Engineering. [13] Yuqiang Li and Qianxing Xiong, “Dijkstra Algorithm Implementing Services Composing Way Selection”, Intelligent Systems and Applications (ISA), 2010 2nd International Workshop on 22-23 May 2010. [14] Stèphano M. M. Gonçalves, Leomar S. da Rosa and Felipe de S. Marques, “A survey of path search algorithms for VLSI detailed routing”, Circuits and Systems (ISCAS), 2017 IEEE International Symposium on 28-31 May 2017. [15] Jing Zhang, Jia Yu, Xiangju Qu and Yu Wu, “Path planning for carrier aircraft based on geometry and Dijkstra’s algorithm”, Control Science and Systems Engineering (ICCSSE), 2017 3rd IEEE International Conference on 17-19 Aug. 2017. [16] http://www.gitta.info/Accessibiliti/en/h tml/Dijkstra_learningObject1.html