{"id":"arxiv:1808.02591","kind":"preprint","title":"A practical Single Source Shortest Path algorithm for random directed graphs with arbitrary weight in expecting linear time","authors":["Dexin Li"],"author_count":1,"year":2018,"published":"2018-08-08","venue":null,"cited_by":null,"doi":null,"arxiv_id":"1808.02591","nct_id":null,"source_url":"https://arxiv.org/abs/1808.02591","archive_url":"https://space-kitty.com/papers/arxiv:1808.02591","updated":"2018-09-18","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/1808.02591","abstract":"In this paper, I present an algorithm called Raffica algorithm for Single-Source Shortest Path(SSSP). On random graph, this algorithm has linear time complexity(in expect). More precisely, the random graph uses configuration model, and the weights are distributed mostly positively. It is also linear for random grid graphs. Despite I made an assumption on the weights of the random graph, this algorithm is able to solve SSSP with arbitrary weights; when a negative cycle exists, this algorithm can find it out once traversed. The algorithm has a lot of appliances.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}