Keywords:-
Article Content:-
Abstract
Data structures play an important role in problem modeling. Graphs model so many other in different domains, one always has to maximize or minimize the time or either the cost in a routing or scheduling problem.
Transport networks and scheduling problems are two areas where optimization plays a key role.
In this article, we are talking about how to adapt certain types of data by the graph structure. And we study the Shortest Path (SPC) and Longest Path (LPL) problem by applying BELLMAN's algorithms and see how these can be applied in scheduling when it comes to projects. An implementation of these algorithms, as well as an application on scheduling with the Metra Potential Method, in acronym MPM, enrich this article.
References:-
References
Pierre Lopez. Graph Course. 2012. Available online at:
http://www.laas.fr/~lopez/cours/graphes/spedago.html
Pierre Arnoux et al. Graphs for the ES terminal . 2002. Available on the Internet at the following address:
http://www.irem.univmrs.fr/productions/nouveautes.php
Eric Sigward . Introduction to Graph Theory. 2022. Available online http://www.ac-nancy-metz.fr/ensign/maths/m2002/institut/cadre_institut.html
Claude Berge. Graphs. Gauthiers -Villars: Paris. 2013.
Pierre Arnoux et al. Graphs in specialist teaching. Appendix to the accompanying document for the ES final year program. 2011. Available online at the following address: www.cndp.fr/lycee/maths/
Claudine Robert & Olivier Cogis . Graph theory. Beyond the bridges of Königsberg: problems, theorems, algorithms. Paris: Vuibert, 2013.
Roy, B. (1962). Graphes et ordonnancement: Application de la théorie des graphes à l'ordonnancement. Revue Française de Recherche Opérationnelle. This is the original publication describing the MPM method developed by Bernard Roy. It's a foundational reference in project scheduling and operations research.
Wiest, J. D., & Levy, F. K. (1977). A Management Guide to PERT/CPM with GERT/PDM/DCPM and Other Networks. Prentice-Hall. This book includes comprehensive chapters on network-based project scheduling techniques, including MPM and its comparison with PERT and CPM.
Gutiérrez-Benítez, J., et al. (2022). Project Scheduling Using Graph-Based Techniques: A Review. Journal of Modern Project Management. A modern review of graph-based scheduling methods, including MPM applications and extensions.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271.
The classic paper introducing Dijkstra’s algorithm, one of the most used for shortest path problems.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Chapter 24 provides detailed analysis of shortest path algorithms including Dijkstra and Bellman-Ford.
Geisberger, R., Sanders, P., Schultes, D., & Delling, D. (2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In Proceedings of the 7th International Conference on Experimental Algorithms (WEA 2008).
Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
Coursera – Graph Search, Shortest Paths, and Data Structures (Stanford University)
https://www.coursera.org/learn/shortest-paths
GeeksforGeeks – Shortest Path Algorithms
https://www.geeksforgeeks.org/shortest-path-algorithms/
Brilliant.org – Graph Theory