Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
Authors: Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi3758-3766
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To evaluate the practical performance of our algorithm for finding diverse shortest st-paths, we conduct a computational experiment with synthetic and real-world instances. The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time. |
| Researcher Affiliation | Academia | 1 Kyushu University, Fukuoka, Japan 2 Hokkaido University, Sapporo, Japan 3 National Institute of Informatics, Tokyo, Japan 4 Kyoto University, Kyoto, Japan 5 Nagoya University, Nagoya, Japan |
| Pseudocode | No | The paper describes algorithms textually and provides mathematical proofs and theorems, but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | The code is available at https://github.com/Dotolation/diverse-graph-algo. |
| Open Datasets | Yes | SNAP: We selected three directed unweighted graphs from Stanford Large Network Dataset Collection 4: wiki Vote (|V | = 7, 115, |E| = 103, 689), soc-Slashdot0922 (|V | = 82, 168, |E| = 870, 161), and ego-Twitter (|V | = 81306, |E| = 1, 768, 149).DIMACS: We selected two directed edge-weighted graphs from the 9th DIMACS Implementation Challenge Shortest Paths5: NY (|V | = 264, 346, |E| = 733, 846) and FLA (|V | = 1, 070, 376, |E| = 2, 712, 798). |
| Dataset Splits | No | The paper describes selecting random st-pairs and running algorithms on them, but does not provide details on formal train/validation/test dataset splits. |
| Hardware Specification | Yes | a computational experiment was conducted on a computer equipped with Intel(R) Xeon(R) Gold 5122 processor (3.60GHz) and 92GB RAM. |
| Software Dependencies | No | The paper states the implementation was "using Java with JGraph T library (Michail et al. 2020)", but does not provide specific version numbers for Java or the JGraph T library. |
| Experiment Setup | Yes | In principle, the source-sink vertex pair used in each test instance was selected randomly (seed = 2021). However, given an st-pair, if the number of the shortest st paths were less than 3k, the pair was excluded from our experiment, since the point of our discussion is to evaluate the ability to pick k solutions in a diverse manner from the much larger solution set. Likewise, we also excluded st pairs whose average shortest path length (unweighted) falls short of 3 as it is difficult to assess the diversity of such short paths. Using the randomly selected n vertex pairs with n = 400 for each instance, our algorithm and the k-best algorithm were executed. We evaluate processing time (in milliseconds) and the diversity measure (the pair-wise Hamming distance of k shortest paths) for these algorithms. |