Log in

Relevant bibliographies by topics / Shortest paths / Journal articles

Journal articles on the topic 'Shortest paths'

To see the other types of publications on this topic, follow the link: Shortest paths.

Author: Grafiati

Published: 4 June 2021

Last updated: 4 April 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Shortest paths.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Kamiński, Marcin, Paul Medvedev, and Martin Milanič. "Shortest paths between shortest paths." Theoretical Computer Science 412, no. 39 (September 2011): 5205–10. http://dx.doi.org/10.1016/j.tcs.2011.05.021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Torchiani, Carolin, Jan Ohst, David Willems, and Stefan Ruzika. "Shortest Paths with Shortest Detours." Journal of Optimization Theory and Applications 174, no. 3 (July 25, 2017): 858–74. http://dx.doi.org/10.1007/s10957-017-1145-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Lofgren, Christopher B. "Reconstructing shortest paths." Annals of Operations Research 20, no. 1 (December 1989): 179–85. http://dx.doi.org/10.1007/bf02216928.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Klein, Cerry M. "Fuzzy shortest paths." Fuzzy Sets and Systems 39, no. 1 (January 1991): 27–41. http://dx.doi.org/10.1016/0165-0114(91)90063-v.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

CHEN, JINDONG, and YIJIE HAN. "SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS." International Journal of Computational Geometry & Applications 06, no. 02 (June 1996): 127–44. http://dx.doi.org/10.1142/s0218195996000095.

Full text

Abstract:

We present an algorithm for determining the shortest path between any two points along the surface of a polyhedron which need not be convex. This algorithm also computes for any source point on the surface of a polyhedron the inward layout and the subdivision of the polyhedron which can be used for processing queries of shortest paths between the source point and any destination point. Our algorithm uses a new approach which deviates from the conventional “continuous Dijkstra” technique. Our algorithm has time complexity O(n2) and space complexity Θ(n).

APA, Harvard, Vancouver, ISO, and other styles

6

Matthew Carlyle, W., and R. Kevin Wood. "Near-shortest and K-shortest simple paths." Networks 46, no. 2 (2005): 98–109. http://dx.doi.org/10.1002/net.20077.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Goldstone, Richard, Rachel Roca, and Robert Suzzi Valli. "Shortest Paths on Cubes." College Mathematics Journal 52, no. 2 (March 15, 2021): 121–32. http://dx.doi.org/10.1080/07468342.2021.1866944.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Elkin, Michael. "Computing almost shortest paths." ACM Transactions on Algorithms 1, no. 2 (October 2005): 283–323. http://dx.doi.org/10.1145/1103963.1103968.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Cheng, Siu-Wing, and Jiongxin Jin. "Approximate Shortest Descending Paths." SIAM Journal on Computing 43, no. 2 (January 2014): 410–28. http://dx.doi.org/10.1137/130913808.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Barma, M. "Shortest paths in percolation." Journal of Physics A: Mathematical and General 18, no. 6 (April 21, 1985): L277—L283. http://dx.doi.org/10.1088/0305-4470/18/6/003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Wagner, Dorothea, Thomas Willhalm, and Christos Zaroliagis. "Dynamic Shortest Paths Containers." Electronic Notes in Theoretical Computer Science 92 (February 2004): 65–84. http://dx.doi.org/10.1016/j.entcs.2003.12.023.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Dębski, Michał, Konstanty Junosza-Szaniawski, and Zbigniew Lonc. "Bundling all shortest paths." Discrete Applied Mathematics 277 (April 2020): 82–91. http://dx.doi.org/10.1016/j.dam.2019.08.027.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Watkins, Mark E. "Infinite paths that contain only shortest paths." Journal of Combinatorial Theory, Series B 41, no. 3 (December 1986): 341–55. http://dx.doi.org/10.1016/0095-8956(86)90055-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Gajjar, Kshitij, Agastya Vibhuti Jha, Manish Kumar, and Abhiruk Lahiri. "Reconfiguring Shortest Paths in Graphs." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (June 28, 2022): 9758–66. http://dx.doi.org/10.1609/aaai.v36i9.21211.

Full text

Abstract:

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time, so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) revamping road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c) and (d) are restrictions to different graph classes. We show that (a) is intractable, even for relaxed variants of the problem. For (b), (c) and (d), we present efficient algorithms to solve the respective problems. We also generalise the problem to when at most k (for some k >= 2) contiguous vertices on a shortest path can be changed at a time.

APA, Harvard, Vancouver, ISO, and other styles

15

Pijls, W. H. L. M. "Shortest Paths and Game Trees." ICGA Journal 15, no. 2 (June 1, 1992): 82. http://dx.doi.org/10.3233/icg-1992-15209.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Bajaj, Chanderjit, and T. T. Moh. "Generalized Unfoldings for Shortest Paths." International Journal of Robotics Research 7, no. 1 (February 1988): 71–76. http://dx.doi.org/10.1177/027836498800700105.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Narraway, J. J. "Shortest paths in regular grids." IEE Proceedings - Circuits, Devices and Systems 145, no. 5 (1998): 289. http://dx.doi.org/10.1049/ip-cds:19982268.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Eppstein, David. "Finding the k Shortest Paths." SIAM Journal on Computing 28, no. 2 (January 1998): 652–73. http://dx.doi.org/10.1137/s0097539795290477.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Dor, Dorit, Shay Halperin, and Uri Zwick. "All-Pairs Almost Shortest Paths." SIAM Journal on Computing 29, no. 5 (January 2000): 1740–59. http://dx.doi.org/10.1137/s0097539797327908.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Cheng, G., and N. Ansari. "Finding All Hops Shortest Paths." IEEE Communications Letters 8, no. 2 (February 2004): 122–24. http://dx.doi.org/10.1109/lcomm.2004.823365.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Bonifaci, Vincenzo, Kurt Mehlhorn, and Girish Varma. "Physarum can compute shortest paths." Journal of Theoretical Biology 309 (September 2012): 121–33. http://dx.doi.org/10.1016/j.jtbi.2012.06.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Eilam-Tzoreff, Tali. "The disjoint shortest paths problem." Discrete Applied Mathematics 85, no. 2 (June 1998): 113–38. http://dx.doi.org/10.1016/s0166-218x(97)00121-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Arita, Masanori. "Metabolic reconstruction using shortest paths." Simulation Practice and Theory 8, no. 1-2 (April 2000): 109–25. http://dx.doi.org/10.1016/s0928-4869(00)00006-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Conforti, Michele, and Romeo Rizzi. "Shortest paths in conservative graphs." Discrete Mathematics 226, no. 1-3 (January 2001): 143–53. http://dx.doi.org/10.1016/s0012-365x(00)00128-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Feder, Tomás, Rajeev Motwani, Liadan O'Callaghan, Chris Olston, and Rina Panigrahy. "Computing shortest paths with uncertainty." Journal of Algorithms 62, no. 1 (January 2007): 1–18. http://dx.doi.org/10.1016/j.jalgor.2004.07.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Bose, Prosenjit, Anil Maheshwari, Giri Narasimhan, Michiel Smid, and Norbert Zeh. "Approximating geometric bottleneck shortest paths." Computational Geometry 29, no. 3 (November 2004): 233–49. http://dx.doi.org/10.1016/j.comgeo.2004.04.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Efrat, Alon, Stephen G. Kobourov, and Anna Lubiw. "Computing homotopic shortest paths efficiently." Computational Geometry 35, no. 3 (October 2006): 162–72. http://dx.doi.org/10.1016/j.comgeo.2006.03.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Schäfer, Luca E., Tobias Dietz, Nicolas Fröhlich, Stefan Ruzika, and José R. Figueira. "Shortest paths with ordinal weights." European Journal of Operational Research 280, no. 3 (February 2020): 1160–70. http://dx.doi.org/10.1016/j.ejor.2019.08.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Hassin, Rafael, and Nimrod Megiddo. "On orientations and shortest paths." Linear Algebra and its Applications 114-115 (March 1989): 589–602. http://dx.doi.org/10.1016/0024-3795(89)90481-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Lalgudi, Kumar N., and Marios C. Papaefthymiou. "Computing strictly-second shortest paths." Information Processing Letters 63, no. 4 (August 1997): 177–81. http://dx.doi.org/10.1016/s0020-0190(97)00122-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Roditty, Liam, and Uri Zwick. "On Dynamic Shortest Paths Problems." Algorithmica 61, no. 2 (March 3, 2010): 389–401. http://dx.doi.org/10.1007/s00453-010-9401-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Asplund, John, Kossi Edoh, Ruth Haas, Yulia Hristova, Beth Novick, and Brett Werner. "Reconfiguration graphs of shortest paths." Discrete Mathematics 341, no. 10 (October 2018): 2938–48. http://dx.doi.org/10.1016/j.disc.2018.07.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Ghosh, R. K., and G. P. Bhattacharjee. "Parallel algorithm for shortest paths." IEE Proceedings E Computers and Digital Techniques 133, no. 2 (1986): 87. http://dx.doi.org/10.1049/ip-e.1986.0009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Nannicini, Giacomo, and Leo Liberti. "Shortest paths on dynamic graphs." International Transactions in Operational Research 15, no. 5 (September 2008): 551–63. http://dx.doi.org/10.1111/j.1475-3995.2008.00649.x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Chambers, Erin, Brittany Terese Fasy, Yusu Wang, and Carola Wenk. "Map-Matching Using Shortest Paths." ACM Transactions on Spatial Algorithms and Systems 6, no. 1 (February 15, 2020): 1–17. http://dx.doi.org/10.1145/3368617.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Silverbush, D., and R. Sharan. "Network orientation via shortest paths." Bioinformatics 30, no. 10 (January 27, 2014): 1449–55. http://dx.doi.org/10.1093/bioinformatics/btu043.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Desel, J., and J. Esparza. "Shortest Paths in Reachability Graphs." Journal of Computer and System Sciences 51, no. 2 (October 1995): 314–23. http://dx.doi.org/10.1006/jcss.1995.1070.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Burkard, R. E., G. Rote, E. Y. Yao, and Z. L. Yu. "Shortest polygonal paths in space." Computing 45, no. 1 (March 1990): 51–68. http://dx.doi.org/10.1007/bf02250584.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Icking, Christian, Günter Rote, Emo Welzl, and Chee Yap. "Shortest paths for line segments." Algorithmica 10, no. 2-4 (October 1993): 182–200. http://dx.doi.org/10.1007/bf01891839.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Xue, Bing, Liancui Zuo, Guanghui Wang, and Guojun Li. "Shortest paths in Sierpiński graphs." Discrete Applied Mathematics 162 (January 2014): 314–21. http://dx.doi.org/10.1016/j.dam.2013.08.029.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Sedgewick, Robert, and Jeffrey Scott Vitter. "Shortest paths in euclidean graphs." Algorithmica 1, no. 1-4 (November 1986): 31–48. http://dx.doi.org/10.1007/bf01840435.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Papadimitriou, Christos H., and Mihalis Yannakakis. "Shortest paths without a map." Theoretical Computer Science 84, no. 1 (July 1991): 127–50. http://dx.doi.org/10.1016/0304-3975(91)90263-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Ahmed, Mustaq, and Anna Lubiw. "Shortest paths avoiding forbidden subpaths." Networks 61, no. 4 (January 7, 2013): 322–34. http://dx.doi.org/10.1002/net.21490.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Andreatta, Giovanni, and Luciano Romeo. "Stochastic shortest paths with recourse." Networks 18, no. 3 (1988): 193–204. http://dx.doi.org/10.1002/net.3230180306.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

DE QUEIRÓS VIEIRA MARTINS, ERNESTO, MARTA MARGARIDA BRAZ PASCOAL, and JOSÉ LUIS ESTEVES DOS SANTOS. "DEVIATION ALGORITHMS FOR RANKING SHORTEST PATHS." International Journal of Foundations of Computer Science 10, no. 03 (September 1999): 247–61. http://dx.doi.org/10.1142/s0129054199000186.

Full text

Abstract:

The shortest path problem is a classical network problem that has been extensively studied. The problem of determining not only the shortest path, but also listing the K shortest paths (for a given integer K>1) is also a classical one but has not been studied so intensively, despite its obvious practical interest. Two different types of problems are usually considered: the unconstrained and the constrained K shortest paths problem. While in the former no restriction in considered in the definition of a path, in the constrained K shortest paths problem all the paths have to satisfy some condition – for example, to be loopless. In this paper new algorithms are proposed for the uncontrained problem, which compute a super set of the K shortest paths. It is also shown that ranking loopless paths does not hold in general the Optimality Principle and how the proposed algorithms for the unconstrained problem can be adapted for ranking loopless paths.

APA, Harvard, Vancouver, ISO, and other styles

46

Nash, Alex, and Sven Koenig. "Any-Angle Path Planning." AI Magazine 34, no. 4 (September 18, 2013): 85–107. http://dx.doi.org/10.1609/aimag.v34i4.2512.

Full text

Abstract:

In robotics and video games, one often discretizes continuous terrain into a grid with blocked and unblocked grid cells and then uses path-planning algorithms to find a shortest path on the resulting grid graph. This path, however, is typically not a shortest path in the continuous terrain. In this overview article, we discuss a path-planning methodology for quickly finding paths in continuous terrain that are typically shorter than shortest grid paths. Any-angle path-planning algorithms are variants of the heuristic path-planning algorithm A* that find short paths by propagating information along grid edges (like A*, to be fast) without constraining the resulting paths to grid edges (unlike A*, to find short paths).

APA, Harvard, Vancouver, ISO, and other styles

47

Bley, Andreas. "Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths." Networks 50, no. 1 (2007): 29–36. http://dx.doi.org/10.1002/net.20163.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Bailey, James, Craig Tovey, Tansel Uras, Sven Koenig, and Alex Nash. "Path Planning on Grids: The Effect of Vertex Placement on Path Length." Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 11, no. 1 (June 24, 2021): 108–14. http://dx.doi.org/10.1609/aiide.v11i1.12808.

Full text

Abstract:

Video-game designers often tessellate continuous 2-dimensional terrain into a grid of blocked and unblocked square cells. The three main ways to calculate short paths on such a grid are to determine truly shortest paths, shortest vertex paths and shortest grid paths, listed here in decreasing order of computation time and increasing order of resulting path length. We show that, for both vertex and grid paths on both 4-neighbor and 8-neighbor grids, placing vertices at cell corners rather than at cell centers tends to result in shorter paths. We quantify the advantage of cell corners over cell centers theoretically with tight worst-case bounds on the ratios of path lengths, and empirically on a large set of benchmark test cases. We also quantify the advantage of 8-neighbor grids over 4-neighbor grids.

APA, Harvard, Vancouver, ISO, and other styles

49

Rubanova, Natalia, and Nadya Morozova. "Centrality and the shortest path approach in the human interactome." Journal of Bioinformatics and Computational Biology 17, no. 04 (August 2019): 1950027. http://dx.doi.org/10.1142/s0219720019500276.

Full text

Abstract:

Many notions and concepts for network analysis, including the shortest path approach, came to systems biology from the theory of graphs — the field of mathematics that studies graphs. We studied the relationship between the shortest paths and a biologically meaningful molecular path between vertices in human molecular interaction networks. We analyzed the sets of the shortest paths in the human interactome derived from HPRD and HIPPIE databases between all possible combinations of start and end proteins in eight signaling pathways in the KEGG database — NF-kappa B, MAPK, Jak-STAT, mTOR, ErbB, Wnt, TGF-beta, and the signaling part of the apoptotic process. We investigated whether the shortest paths match the canonical paths. We studied whether centrality of vertices and paths in the subnetworks induced by the shortest paths can highlight vertices and paths that are part of meaningful molecular paths. We found that the shortest paths match canonical counterparts only for canonical paths of length 2 or 3 interactions. The shortest paths match longer canonical counterparts with shortcuts or substitutions by protein complex members. We found that high centrality vertices are part of the canonical paths for up to 80% of the canonical paths depending on the database and the length.

APA, Harvard, Vancouver, ISO, and other styles

50

Botea, Adi, Massimiliano Mattetti, Akihiro Kishimoto, Radu Marinescu, and Elizabeth Daly. "Counting Vertex-Disjoint Shortest Paths in Graphs." Proceedings of the International Symposium on Combinatorial Search 12, no. 1 (July 21, 2021): 28–36. http://dx.doi.org/10.1609/socs.v12i1.18548.

Full text

Abstract:

Finding a shortest path in a graph is at the core of many combinatorial search problems. A closely related problem refers to counting the number of shortest paths between two nodes. Such problems are solvable in polynomial time in the size of the graph. However, more realistic problem formulations could additionally specify constraints to satisfy. We study the problem of counting the shortest paths that are vertex disjoint and can satisfy additional constraints. Specifically, we look at the problems of counting vertex-disjoint shortest paths in edge-colored graphs, counting vertex-disjoint shortest paths with directional constraints, and counting vertex-disjoint shortest paths between multiple source-target pairs. We give a detailed theoretical analysis, and show formally that all of these three counting problems are NP-complete in general.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!