Geometric Approach to Optimal Path Problem with Uncertain Arc Lengths

  • Authors

    • Atefeh Hasan-Zadeh University of Tehran
    2020-07-25
    https://doi.org/10.14419/jacst.v9i1.30674
  • Shortest path problem, Homotopy, Covering space, Cycle

  • In this paper, the problem of finding the shortest paths, one of the most important problems in science and technology has been geometrically studied. Shortest path algorithm has been generalized to the shortest cycles in each homotopy class on a surface with arbitrary topology, using the universal covering space notion in the algebraic topology. Then, a general algorithm has been presented to compute the shortest cycles (geometrically rather than combinatorial) in each homotopy class. The algorithm can handle surface meshes with the desired topology, with or without boundary. It also provides a fundamental framework for other algorithms based on universal coverage space due to the capacity and flexibility of the framework.

     

  • References

    1. [1] Bellman E, (1958), On a routing problem, Quarterly of Applied Mathematics, 16(1), 87–90.

      [2] Dijkstra EW, (1959), A note on two problems in connection with graphs, Numerical Mathematics, 1(1), 269–271.

      [3] Dreyfus S, (1969), An appraisal of some shortest path algorithms, Operations Research, 17(3), 395–412

      [4] Floyd RW, (1962), Algorithm-97-shortest path, Communications of the ACM, 5(6), 345.

      [5] Frank H, (1969), Shortest paths in probability graphs, Operations Research, 17(4), 583–599.

      [6] Hall R, (1986), The fastest path through a network with random time-dependent travel time, Transportation Science, 20(3), 182–188.

      [7] Loui P, (1983), Optimal paths in graphs with stochastic or multidimensional weights, Communications of the ACM, 26(9), 670–676.

      [8] Mirchandani PB, (1976), Shortest distance and reliability of probabilistic networks, Computers & Operations Research, 3(4), 347–676.

      [9] Dubois D, Prade H, Fuzzy Sets and Systems: Theory and Applications, Academic Press, New York, 1980.

      [10] Klein CM, Fuzzy shortest paths, Fuzzy Sets and Systems, 39(1), 27–41.

      [11] Ji X & Iwamura K, (2007), New models for shortest path problem with fuzzy arc lengths, Applied Mathematical Modelling, 31(2), 259–269.

      [12] Baoding Liu, Uncertainty Theory, 2007, Springer

      [13] Idri A, Oukarfi M, Boulmakul A, Zeitouni K & Masri A, (2017), A new time-dependent shortest path algorithm for multimodal transportation network, Procedia Computer Science, 109C, 692–697.

      [14] Shirdel G & Rezapour H, (2017), Approximate solutions for time-varying shortest path problem, Communications in Combinatorics and Optimization, 2(2), 39-147.

      [15] Yang Y, Li Z, Wang X & Hu Q, (2019), Finding the Shortest Path with Vertex Constraint over Large Graphs, Complexity, https://doi.org/10.1155/2019/8728245

      [16] Cormen TH, Leiserson CE, Rivest RL & Stein C, Introduction to algorithms, Massachusetts Institute of technology, 2001.

      [17] Baras JS, Theodorakopoulos G & Walrand J, Path Problems in Networks, Morgan and Claypool, 2010.

      [18] Hasan-Zadeh A, (2019), Geometric Modelling of the Thinning by Cell Complexes, Journal of Advanced Computer Science & Technology, 8(2), 38-39.

      [19] Hatcher, Algebraic Topology, Cambridge University Press, 2001.

  • Downloads

    Additional Files

  • How to Cite

    Hasan-Zadeh, A. (2020). Geometric Approach to Optimal Path Problem with Uncertain Arc Lengths. Journal of Advanced Computer Science & Technology, 9(1), 11-13. https://doi.org/10.14419/jacst.v9i1.30674