8000
Skip to content

    • mike-liuliu/shortest_path_warm_start

    BranchesTags

    Folders and files

    NameName
    Last commit message
    Last commit date

    Latest commit

     

    History

    18 Commits
    C_plus_plus_code
    C_plus_plus_code
     
     
    data
    data
     
     
    funcs
    funcs
     
     
    .DS_Store
    .DS_Store
     
     
    0 Dump and load distance matrix by csv file.ipynb
    0 Dump and load distance matrix by csv file.ipynb
     
     
    1 Solving the all pairs shortest path problem with Algorithm 1.ipynb
    1 Solving the all pairs shortest path problem with Algorithm 1.ipynb
     
     
    10 Warm-start calculation of path - shortest path problem.ipynb
    10 Warm-start calculation of path - shortest path problem.ipynb
     
     
    11 Warm-start calculation of path - minimax path problem.ipynb
    11 Warm-start calculation of path - minimax path problem.ipynb
     
     
    12 Warm-start calculation of path - minimax path problem- check size of candidate_node_list.ipynb
    12 Warm-start calculation of path - minimax path problem- check size of candidate_node_list.ipynb
     
     
    13 Warm-start calculation of path - widest path problem.ipynb
    13 Warm-start calculation of path - widest path problem.ipynb
     
     
    14 Warm-start calculation of path - widest path problem - check correctness.ipynb
    14 Warm-start calculation of path - widest path problem - check correctness.ipynb
     
     
    15 Warm-start calculation of all shortest paths.ipynb
    15 Warm-start calculation of all shortest paths.ipynb
     
     
    16 Warm-start calculation of all minimax paths.ipynb
    16 Warm-start calculation of all minimax paths.ipynb
     
     
    17 Warm-start calculation of all widest paths.ipynb
    17 Warm-start calculation of all widest paths.ipynb
     
     
    18 Cold-start calculation of all shortest paths on undirected graph.ipynb
    18 Cold-start calculation of all shortest paths on undirected graph.ipynb
     
     
    19 Warm-start calculation of all shortest paths - further optimized.ipynb
    19 Warm-start calculation of all shortest paths - further optimized.ipynb
     
     
    2 Test warm-start calculation of the APSP matrix by Algorithm 1 in directed graph.ipynb
    2 Test warm-start calculation of the APSP matrix by Algorithm 1 in directed graph.ipynb
     
     
    20 Cold-start calculation of all shortest paths on undirected graph - further optimized.ipynb
    20 Cold-start calculation of all shortest paths on undirected graph - further optimized.ipynb
     
     
    21 All shortest paths calculated by Algorithm 8 may be incomplete.ipynb
    21 All shortest paths calculated by Algorithm 8 may be incomplete.ipynb
     
     
    22 Test remove node - shortest path problem - algorithm 10.ipynb
    22 Test remove node - shortest path problem - algorithm 10.ipynb
     
     
    23 Test remove node - shortest path problem - algorithm 11.ipynb
    23 Test remove node - shortest path problem - algorithm 11.ipynb
     
     
    24 Test remove node - Algorithm 11 - variant 1.ipynb
    24 Test remove node - Algorithm 11 - variant 1.ipynb
     
     
    25 Test remove node - Algorithm 11 - variant 2.ipynb
    25 Test remove node - Algorithm 11 - variant 2.ipynb
     
     
    26 Test vary edge - shortest path problem - using Algorithm 11.ipynb
    26 Test vary edge - shortest path problem - using Algorithm 11.ipynb
     
     
    27 Revising Algorithm 8 for solving the K shortest path problem.ipynb
    27 Revising Algorithm 8 for solving the K shortest path problem.ipynb
     
     
    28 Test remove node - shortest path problem - mix Algorithm 5 and 10.ipynb
    28 Test remove node - shortest path problem - mix Algorithm 5 and 10.ipynb
     
     
    3 Test Algorithm 1 for solving the APSP matrix when the graph has negative weights.ipynb
    3 Test Algorithm 1 for solving the APSP matrix when the graph has negative weights.ipynb
     
     
    4 Test remove node - shortest path problem.ipynb
    4 Test remove node - shortest path problem.ipynb
     
     
    5 Test remove node - minimax path problem.ipynb
    5 Test remove node - minimax path problem.ipynb
     
     
    6 Test remove node - widest path problem.ipynb
    6 Test remove node - widest path problem.ipynb
     
     
    7 Test vary edge - shortest path problem.ipynb
    7 Test vary edge - shortest path problem.ipynb
     
     
    8 Test vary edge - minimax path problem.ipynb
    8 Test vary edge - minimax path problem.ipynb
     
     
    9 Test vary edge - widest path problem.ipynb
    9 Test vary edge - widest path problem.ipynb
     
     
    LICENSE.txt
    LICENSE.txt
     
     
    README.txt
    README.txt
     
     
    requirements.txt
    requirements.txt
     
     

    Repository files navigation

    0. This is the source code of the paper "Solving the all pairs shortest path problem after minor update of a large dense graph."
 
1. License.
   
License of the source code : Apache License, Version 2.0
 
2. Citation:
 
@article{liu2024solving,
  title={Solving the all pairs shortest path problem after minor update of a large dense graph},
  author={Liu, Gangli},
  journal={arXiv preprint arXiv:2412.15122},
  year={2024},
  url={https://arxiv.org/abs/2412.15122},
}

    About

    Source code of the paper "Solving the all pairs shortest path problem after minor update of a large dense graph."

    arxiv.org/abs/2412.15122

    Topics

    shortest-path-problem all-pairs-shortest-path widest-path-problem minimax-path-problem

    Resources

    Readme

    License

    Apache-2.0 license
    Activity

    Stars

    3 stars

    Watchers

    1 watching

    Forks

    0 forks
    Report repository

    Releases

    No releases published

    Packages

     
     
     

    Contributors

    Languages
    0