Vol. 6 No. 1 (2020): Γεω-Αναφορές
Articles

Determination of the shortest path in the university campus of Serres using the Dijkstra and Bellman‐Ford algorithms

PDF
  • Dimitrios Botsis,
  • Eleftherios Panagiotopoulos
Categories

Published 2025-10-15

Keywords

  • αλγόριθμος Dijkstra,
  • αλγόριθμος Bellman‐ Ford,
  • γράφοι,
  • συντομότερη διαδρομή,
  • χάρτες διαδρομών

Copyright (c) 2020 Dimitrios Botsis, Eleftherios Panagiotopoulos

Creative Commons License

This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

How to Cite

Dimitrios Botsis, & Eleftherios Panagiotopoulos. (2025). Determination of the shortest path in the university campus of Serres using the Dijkstra and Bellman‐Ford algorithms. CHORO-grafies, 6(1), 033-042. https://doi.org/10.5281/a6dacy24

Abstract

Στην παρούσα ερευνητική εργασία παρουσιάζεται η εφαρμογή των αλγόριθμων Dijkstra και Bellman‐Ford στο χώρο των εγκαταστάσεων της πανεπιστημιούπολης Σερρών του Διεθνούς Πανεπιστημίου Ελλάδος, για την προσέγγιση των συντομότερων διαδρομών από επιλεγμένες θέσεις, σε διάφορα κτίρια. Οι εγκαταστάσεις του εκπαιδευτικού ιδρύματος αναπαραστάθηκαν με τη μορφή γράφου, του οποίου οι κορυφές είναι επιλεγμένες θέσεις και κτίρια, ενώ οι ακμές είναι οι διαδρομές, με τα βάρη τους να αντιπροσωπεύουν τα μήκη τους. Η λήψη αποφάσεων για τη δημιουργία των βέλτιστων διαδρομών και ο σχεδιασμός χαρτών με αποτυπωμένες τις προτεινόμενες διαδρομές, αποτελούν ένα πολύπλοκο πρόβλημα το οποίο μπορεί να επιλυθεί με την εφαρμογή αλγόριθμων συντομότερων μονοπατιών. Συμπερασματικά, η εφαρμογή των αλγόριθμων Dijkstra και Bellman‐Ford έδειξε ότι είναι αποτελεσματικοί για την προσέγγιση των βέλτιστων – συντομότερων διαδρομών και μπορούν να εφαρμοστούν με επιτυχία στο σχεδιασμό πολυπλοκότερων διαδρομών. Τέλος η εφαρμογή δύο διαφορετικών αλγορίθμων που προσεγγίζουν το ίδιο πρόβλημα επιτρέπει την επιβεβαίωση της εγκυρότητας των αποτελεσμάτων τους 

PDF

Downloads

Download data is not yet available.

References

  1. ‘’A faster algorithm for the single source shortest path problem with few distinct positive lengths’’, J.B. Orlin, K. Madduri, K. Subramani, M. Williamson, Journal of Discrete Algorithms, Vol. 8, Nr. 2, 2010, pp. 189–198. https://doi.org/10.1016/j.jda.2009.03.001.
  2. ‘’Routing Choice Modelling using Fuzzy Logic and Adaptive Neuro‐Fuzzy’’, K.D. Subodh, M. Deval, S.A. Shriniwa, P.S. Ajit, K.S. Ashoke, Modern Traffic and Transportation, Engineering Research, Vol. 2, Nr. 4, 2013, pp. 91–99.
  3. ‘’Faster algorithms for the shortest path problem’’, K.R. Ahuja, K. Mehlhorn, B.J. Orlin, E.R. Tarjan, Journal of the ACM, Vol. 37, Nr. 2, 1990, pp. 213–223. https://doi.org/10.1145/77600.77615.
  4. ‘’Data Structures and Algorithms: Concepts, Techniques and Applications’’, G.A.V. Pai, Tata McGraw‐Hill Education Private Limited, New Delhi, India, 2010.
  5. ‘’On the History of the Shortest Path Problem’’, A. Schrijver, Documenta Mathematica, 2010, pp. 172.
  6. ‘’Calibration and validation of a simulation‐based dynamic traffic assignment model for a large‐scale congested network’’, S. Shafiei, Z. Gu, M. Saberi, Simulation Modelling Practice and Theory, Vol. 86, 2018, pp. 169‐186. https://doi.org/10.1016/j.simpat.2018.04.006.
  7. ‘’Energy and mobility conscious multipath routing scheme for route stability and load balancing in MANETs’’, W.A. Jabbar, M. Ismail, R. Nordin, Simulation Modelling Practice and Theory, Vol. 77, 2017, pp. 245‐271. http://dx.doi.org/10.1016/j.simpat.2017.07.001.
  8. ‘’A Note of Two Problems in Connexion with Graph’’, E.W. Dijkstra, Numerische Mathematik, Vol. 1, 1959, pp. 23‐33. https://doi.org/10.1007/BF01386390.
  9. ‘’An Interview with Edsger W. Dijkstra’’, P. Frana, Communication of the ACM, Vol. 53, Nr. 8, 2010, pp. 41‐47. https://doi.org/10.1145/1787234.1787249.
  10. ‘’Route Planning in Vanet By Comparative Study of Algorithms’’, J. Shivani, J. Singh, International Journal of Advanced Research in Computer Science and Software Engineering, Vol. 3, Nr. 7, 2013, pp. 682‐689.
  11. ‘’The Utilization of Dijkstra’s Algorithm to Assist Evacuation Route in Higher and Close Building’’, N.A.M. Sabri, A.S.H. Basari, B. Husin, K.A.F.A. Samah, Journal of Computer Science, Vol. 11, Nr. 2, 2015, pp. 330–336. https://doi.org/10.3844/jcssp.2015.330.336.
  12. ‘’An Investigation of Dijkstra and Floyd Algorithms in National City Traffic Advisory Procedures’’, A.K. Sangaiah, M. Han, S. Zhang, International Journal of Computer Science and Mobile Computing, Vol. 3, Nr. 2, 2014, pp. 124‐138.
  13. ‘’Review of Graph Theory Algorithms’’, Ν. Meghanathan, Department of Computer Science, Jackson State University, 2012.
  14. ‘’Railway Route Optimization System using Dijkstra’s Method’’, P. Pramod, D. Sunanda, International Journal on Recent and Innovation Trends in Computing and Communication, Vol. 2, Nr. 3, 2014, pp. 3435‐3440.
  15. ‘’Using modified Dijkstra’ s algorithm for critical path method in a project network’’, N.R. Shankar, V. Sireesha, Int. J. Comput. Appl. Math., Vol. 5, Nr. 2, 2010, pp. 217–225.
  16. ‘’Comparison of Dijkstra’ s shortest path algorithm with genetic algorithm for static and dynamic routing network’’, Y. Sharma, S.C. Saini, M. Bhandhari, Int. J. Electron. Comput. Sci. Eng., Vol. 1, Nr. 2, 2012, pp. 416–425.
  17. Xu Y., Wang Z., Zheng Q., Han, Z., ‘’The application of Dijkstraʹs algorithm in the intelligent fire evacuation system’’, in 4th International Conference on Intelligent Human‐Machine Systems and Cybernetics 2012, 1, pp. 3–6. doi:10.1109/IHMSC.2012.7.
  18. ‘’The Trace Model: A model for simulation of the tracing process during evacuations in complex route environments’’, W. Li, Y. Li, P. Yu, J. Gong, S. Shen, Simulation Modelling Practice and Theory, Vol. 60, 2016, pp. 108‐121. https://doi.org/10.1016/j.simpat.2015.09.011.
  19. ‘’Optimal route selection model for fire evacuations based on hazard prediction data’’, M. Choi, S. Chi, Simulation Modelling Practice and Theory, Vol. 94, 2019, pp. 321‐333. https://doi.org/10.1016/j. simpat.2019.04.002.
  20. ‘’Modification of Dijkstraʹs algorithm for safest and shortest path during emergency evacuation’’, K.A.F.A. Samah, B. Hussin, A.S.H. Basari, Applied Mathematical Sciences, Vol. 9, Nr. 31, 2015, pp. 1531–1541. http://dx.doi.org/10.12988/ams.2015. 49681.
  21. ‘’The application of the shortest path algorithm in the evacuation system’’, T.Y. Wang, R. Huang, L. Li, W.G. Xu, J.G. Nie, In Information Technology, Computer Engineering and Management Sciences (ICM) 2011, 2 IEEE, 2011, pp. 250–253. doi:10.1109/ICM.2011.119.
  22. ‘’Optimizing Paths Taken Across Campus With Respect to Distance and Weather’’, H. Gao, D. Wu, B. Zhang, 21‐393 Final Project, 2014.
  23. ‘’Application of Dijkstra algorithm to proposed tramway of a potential world class university’’, M.C. Agarana, N.C. Omoregbe, M.O. Ogunpeju, Applied Mathematics, Vol. 7, 2016, pp. 496–503. https://doi.org/10.4236/am.2016.76045.
  24. Lateef U.O., Adedeji A., Kazeem R., Idowu P.A., ‘’Determination of the shortest path of a Nigerian university map using Dijkstra’s algorithm’’, 11th International Multi‐Conference on ICT Applications, 2017, AICTRRA.
  25. ‘’A Review of Application of Graph Theory for Network’’, A.B. Sadavare, R.V. Kulkarni, International Journal of Computer Science and Information Technologies, Vol. 3, Nr. 6, 2012, pp. 5296‐5300.
  26. Kariotis G., Theodoridou L., Kariotou G., Panagiotopoulos E., ‘’From suspicion to coexistence ‐ The Municipality of Serres and the Τ.Ε.Ι. campus Serres (1979‐2009)’’, Proceedings of the 1st Panhellenic Conference with international participation and theme: Local Communities and Higher Education Institutions: Coexistence for Sustainable Development, Rhodes, 2010 April 24‐25.
  27. ‘’Machine Learning: A Bayesian and Optimization Perspective’’, S. Theodoridis, Academic Press, Elsevier, 2015.
  28. ‘’Bellman Ford Algorithm, MATLAB Central File Exchange’’, A. Rath, 2020, https://www.mathworks.com/matlabcentral/fileexchange/63069‐bellman‐ford‐algorithm.