Vous êtes ici :

AccueilRessources Bibliographie sur le problème du plus court chemin

Bibliographie sur le problème du plus court chemin

Bibliographie structurée, à jour et commentée à venir.

Voici quelques éléments pour commencer :


  • [1] E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik, 1959.
  • [2] E.L Johnson, "On shortest paths and sorting", Proc. 25th ACM Annual Conference, p.510-517, 1972
  • [3] R.B. Dial, "Algorithm 360: Shortest path forest with topological ordering", Communications of the A.C.M. 12, p.632-633, 1969
  • [4] M.S. hung, J.J. Divoky, "A computational study of efficient shortest path algorithms", Computers and Operations Research, vol 15, n°6, p.567-576, 1988
  • [5] Ahuja, Melhorn, Orlin, Tarjan, "Faster algorithms for the shortest path problem", Technical Report 193, MIT Operations Research Center, 1988
  • [6] Ahuja, Melhorn, Orlin, Tarjan, "Faster algorithms for the shortest path problem", Journal of the ACM, 37, p.213-223, 1990
  • [7] R. Bellman, "On a routing problem", Quarterly Applied Mathematics 16, p.87-90, 1958
  • [8] L.R. Ford Jr., "Network flow theory", Rand Co., p.293, 1956
  • [9] E.F Moore, "The shortest path through a maze", Proc. International Symposium on Theory of Switching, part 2, Harvard Univ. Press, p.285-292, 1959
  • [10] U. Pape, "Implementation and efficiency of Moore-algorithms for the shortest route problem", Mathematical Programming, 7, p.212-222, 1974
  • [11] Pallottino, "Shortest path methods: Complexity, interrelations and new propositions", Networks 14, p.257-267, 1984
  • [12] F. Glover, R. Glover and D. Klingman, "Computational study of an improved shortest path algorithm", Networks 14, p. 25-36, 1984
  • [13] D.P. Bertsekas, "A simple and fast label correcting algorithm for shortest paths", Networks 23, p. 703-709, 1993
  • [14] A.V. Goldberg, T. Radzik, "A heuristic improvement of the Bellman-Ford algorithm", Applied Mathematics Litters 6, n°3, p.3-6, 1993
  • [15] P.E. Hart, N.J. Nilsson, B. Raphael, "A formal basis for the heuristic determination of minimum cost paths, IEEE Transaction, System Science and Cybernetics", 1968
  • [16] J.L. Bander, C.C White, "A heuristic search algorithm for path determination with learning, IEEE Transactions on Systems, Man and Cybernetics, Part A : Systems and Humans", 1998
  • [17] R. Jacob, M. Marathe, K. Nagel, "A computational study of routing algorithms for realistic transportation networks", Journal of Experimental Algorithmics 4, p. 1-19, 1999
  • [18] G.B. Dantzig, "On the shortest route through a network", Management Science, 1960
  • [19] J.A.T. Nicholson "Finding the shortest route between two points in a network", Computer Journal, 1966.
  • [20] I. Pohl, "Bi-directional search", Machine Intelligence, 1971
  • [21] L. Fu, "Real-time vehicle routing and scheduling in dynamic and stochastic traffic networks", Unpublished Ph.D. Dissertation, University of Alberta, Edmonton, Alberta, 1996
  • [22] D.Wagner et T. Willhalm, "Geometric speed-up techniques for finding shortest paths in large sparse graphs". In 11th European Symposium on Algorithms (ESA 2003), 2003.
  • [23] A. Goldberg et C. Harrelson, "Computing the shortest path : A* search meets graph theory", Rapport technique, Microsoft Research, mars 2003
  • [24] L. Fu, D. Sun et L.R. Rilett, "Heuristic shortest path algorithms for transportation applications : State of the art", Computers and Operations Research, 2005
  • [25] S. Pallottino, M.G. Scutellà, "Equilibrium and Advanced Transportation Modelling", chapter Shortest path algorithms in transportation models : classical and innovative aspects,   p. 245-281, Kluwer Academic Publishers, 1998.
  • [26] B. C. Dean, "Shortest paths in FIFO time-dependent networks : Theory and algorithms", Rapport technique, Massachusetts Institute of Technology, 2004.
  • [27] A. K. Ziliaskopoulos et H. S. Mahmassani, "Time-dependent shortest path algorithm for real-time intelligent vehicle highway system applications", Transportation Research Record : Journal of the Transportation Research Board, 1993.
  • [28] G. Nannicini, D. Delling, D. Schultes et L. Liberti, "Bidirectional A* search on time-dependent road networks", Lecture Notes in Computer Science, 2008.
  • [29] I. Chabini et S. Lan, "Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks", IEEE Transactions on Intelligent Transportation Systems, 2002.
  • [30] F. Schulz, D.Wagner et C. Zaroliagis, "Using multilevel graphs for timetable information in railway systems", In Proceedings of the 4th workshop on algorithms engineering and experiments (ALENEX), 2002.
  • [31] D. Delling et D.Wagner, "Landmark based routing in dynamic graphs", Lecture Notes in Computer Science, 2007.
  • [32] R. W. Hall. "The fastest path through a network with random time-dependent travel times". Transportation Science, 20(3):91–101, 1986.
  • [33] H. N. Psaraftis and J. N. Tsitsiklis. "Dynamic shortest paths in acyclic networks with markovian arc costs". Operations Research, 41(1):91–101, 1993.
  • [34] E. D. Miller-Hooks and H. S. Mahmassani. "Least expected time paths in stochastic, time-varying transportation networks". Transportation Science, 34(2):198–215, 2000.
  • [35] I. Chabini. "Minimum expected travel times in stochastic time-dependent networks revisited". Internal Report. MIT, Cambridge, MA, 2000.
  • [36] S. Nguyen et S. Pallottino, "Equilibrium traffic assignment for large scale transit network", European Journal of Operational Research, p. 176-186, 1988.
  • [37] C. Berge, "Graphs and Hypergraphs", North-Holland Publishing Company, 1973.
  • [38] A. Di Febbraro, S. Sacone, "An on-line information system to balance traffic flows in urban areas", Proceeding of the 36th IEEE conference on decision and control, 1995
  • [39] A. Lozano et G. Storchi, "Shortest viable hyperpath in multimodal networks", Transportation Research, 2002.
  • [40] Italiano, G.F. and U. Nanni: On line maintenance of minimal directed hypergraphs, Proc. 3º Convegno Italiano di Informatica Teorica, Mantova, World Science Press (1989), 335-349
  • [41] B. Jourquine, M. Beuthe, "Transportation policy analysis with a geographic information system: the virtual network of freight transportation in Europe", Transportation Research, 1996.
  • [42] A. Ziliaskopoulos, W. Wardell, "An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays", European Journal of Operational Research, 2000.
  • [43] T. Cormen, C. Leiserson, R. Rivest and C. Stein, "Introduction à l'algorithmique", Edition Dunod, 2002.
  • [44] P. Lacomme, C. Prins et M. Sevaux, "Algorithmes de graphes", EYROLLES, 2003.
  • [45] C. Barrett, R. Jacob et M. Marathe, "Formal language constrained path problems", In Scandinavian Workshop on Algorithm Theory, 1998.
  • [46] H. D. Sherali, Antoine G. Hobeika et S. Kangwalklai, "Time-dependent, label-constrained shortest path problems with applications", Transportation Science, 2003.
  • [47] S. Namkoong, J.H. Rho et J.U. Choi, "Development of the tree-based link labeling algorithm for optimal path-finding in urban transportation networks". Mathematical and computer modelling, 1998.
  • [48] E. Gutiérrez et A. L. Medaglia, "Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks", Annals of Operations Research, 2008
  •  [49] R. F. Kirby et R. B. Potts, "The minimum route problem for networks with turn penalties and prohibitions", Transportation Research, 1969.
  • [50] A. Ziliaskopoulos, H. S. Mahmassani, "A note on least time path computation considering delays and prohibitions for intersection movements", Transportation Research Part B, 1996.
  • [51] D. Villeneuve, G. Desaulniers, "The shortest path problem with forbidden paths", European Journal of Operational Research, 2005.
  • [52] H. D. Sherali, Antoine G. Hobeika et S. Kangwalklai, "Time-dependent, label-constrained shortest path problems with applications", Transportation Science, 2003.
  • [53] M. Bielli, A. Boulmakoul et H. Mouncif, "Object modelling and path computation for multimodal travel systems", European Journal of Operational Research, 2006.
  • [54] A. Lozano et G. Storchi, "Shortest viable path algorithm in multimodal networks", Transportation Research, 2001.
  • [55] R.E. Steuer and E.-U. Choo, "An interactive weighted Tchebycheff procedure for multiple objective programming", Mathematical Programming, 26, 326–344, (1983).
  • [56] Galand, L. and Perny, P. (2006). "Search for compromise solutions in multiobjective state space graphs". pp. 93.
  • [57] Grabish, M. (2006). "L’utilisation de l’intégrale de Choquet en aide multicritère à la décision". European Working Group Multiple Criteria Decision Aiding, 3, 5–10.
  • [58] Current, J., ReVelle, C., and Cohon, J. (1990). "An interactive approach to identify the best compromise solution for two objective shortest path problems". Computers & Operations Research, 17:187{198.
  • [59] Murthy, I. and Olson, D. (1994). "An interactive procedure using domination cones for bicriterion shortest path problems". European Journal of Operational Research, 72:417{431.
  • [60] Henig, M. (1994), "Efficient interactive methods for a class of multiattribute shortest path problems". Management Science, 40:891{897.
  • [61] Coutinho-Rodrigues, J., Climaco, J., and Current, J. (1999). "An interactive bi-objective shortest path approach: searching for unsupported non dominated solutions". Computers & Operations Research, 26:789{798.
  • [62] Hansen, P. (1980). "Bicriterion path problems". pp. 109.
  • [63] P. Hansen, B. Jaumard, and T. Vovor. "Solving the bicriterion shortest path problem from both ends". Technical Report G-98-17, GERAD, 1998.
  • [64] Martins, E. (1984). "On a multicriteria shortest path problem. European Journal of Operational Research", 16(2), 236–245.
  • [65] E. Q. V. Martins and J. L. E. dos. Santos, "The labeling algorithm for the multiobjective shortest path problem", 1999.
  • [66] Guerriero, F. and Musmanno, R. (2001). "Label correcting methods to solve multicriteria shortest path problems". Journal of Optimization Theory and Applications, 111(3), 589–613
  • [67] Stewart, B. and White III, C. (1991). "Multiobjective A*". Journal of the ACM (JACM), 38(4), 814.
  • [68] Mandow, L. and de la Cruz, J. (2005). "A New Approach to Multiobjective A* Search". 19, 218.
  • [69] Berger, A., Grimmer, M. and Müller-Hannemann, M. (2010). "Fully Dynamic Speed-Up Techniques for Multi-criteria Shortest Path Searches in Time-Dependent Networks". Experimental Algorithms, pp. 35–46.
  • [70] Muller-Hannemann, M. and Schnee, M. (2007). "Finding all attractive train connections by multi-criteria Pareto search". Lecture Notes In Computer Science, 4359, 246.
  • [71] Papadimitriou, C. and Yannakakis, M. (2000). "On the Approximability of Trade-offs and Optimal Access of Web Sources (Extended Abstract)". pp. 86.
  • [72] Warburton,A. (1987). "Approximation of Pareto optima in multiple-objective, shortest path problems". Operations Research, pp. 70–79.
  • [73] Tsaggouris, G. and Zaroliagis, C. (2005). "Improved FPTAS for multiobjective shortest paths with applications". CTI Techn. Report TR-2005/07/03.
  • [74] P. Modesti and A. Sciomachen. "A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks". European Journal of Operational Research, 111, p. 495–508, 1998.
  • [75] H. M. Foo, H. W. Leong, Y. Lao, et H. C. Lau. “A Multi-Criteria, Multi-Modal Passenger Route Advisory System”, In Proc. 1999 IES-CTR Int'l Symp., Singapore, 1999
  •  [76] D. Costelloe, P. Mooney and A. Winstanley. "Multiobjective optimisation on transportation networks, technical report: NUIM-CS-TR-2001-08", 2001.





25 Avenue F. Mitterrand, 69675 Bron cedex

T : 04 78 65 68 70




Vers le haut