Abstract
In this paper we study the relationship between Constraint Programming (CP) and Shortest Path (SP) problems. In particular, we show that classical, multicriteria, partially ordered, and modality-based SP problems can be naturally modeled and solved within the Soft Constraint Logic Programming (SCLP) framework, where logic programming is coupled with soft constraints. In this way we provide this large class of SP problems with a high-level and declarative linguistic support whose semantics takes care of both finding the cost of the shortest path(s) and also of actually finding the path(s). On the other hand, some efficient algorithms for certain classes of SP problems can be exploited to provide some classes of SCLP programs with an efficient way to compute their semantics.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bistarelli, S., U. Montanari, and F. Rossi. (1995). “Constraint Solving over Semirings.” In proc. IJCAI95. San Matco, CA: Morgan Kaufman.
Bistarelli, S., U. Montanari, and F. Rossi. (1997a). “Semiring-based Constraint Logic Programming.” In proc. IJCAI97. San Matco, CA: Morgan Kaufman.
Bistarelli, S., U. Montanari, and F. Rossi. (1997b). “Semiring-based Constraint Solving and Optimization.” Journal of the ACM 44(2), 201–236.
Dreyfus, S.E. (1969). “An Appraisal of Some Shortest-Paths Algorithms.” Operation Research 17, 395–412.
Floyd, R.W. (1962). Algorithm 97: Shortest Path: Communication of ACM 5, 345.
Georget, Y. and P. Codognet. (1998). “Compiling Semiring-Based Constraints with clp (fd,s).” In CP98, Springer. LNCS 1520.
Jaffar, J. and J. L. Lassez. (1987). “Constraint Logic Programming.” In Proc. POPL. New York: ACM.
Leiserson, C.E., T.H. Cormen, and R.L. Rivest. (1990). Introduction to Algorithms, ch. 26. Cambridge, MA: MIT Press.
Lloyd, J.W. (1987). Foundations of Logic Programming. Berlin: Springer Verlag.
Pallottino, S. and M.G. Scutellà. (1988). “Shortest Path Algorithms in Transportation Models: Classical and Innovative Aspects. In P. Marcotte and S. Nguyen (eds.), Equilibrium and Advanced Transportation Modelling. pp. 245–281.
Smyth, M.B. (1978). “Power Domains.” Journal of Computer and System Sciences 16(1), 23–36.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bistarelli, S., Montanari, U. & Rossi, F. Soft Constraint Logic Programming and Generalized Shortest Path Problems. Journal of Heuristics 8, 25–41 (2002). https://doi.org/10.1023/A:1013609600697
Issue Date:
DOI: https://doi.org/10.1023/A:1013609600697