Solving shortest paths efficiently on nearly acyclic directed graphs.
Shane SaundersTadao TakaokaPublished in: Theor. Comput. Sci. (2007)
Keyphrases
- shortest path
- directed graph
- shortest path problem
- random walk
- shortest path algorithm
- flow graph
- road network
- directed acyclic graph
- edge weights
- np hard
- strongly connected
- maximum flow
- graph structure
- weighted graph
- optimal path
- disjoint paths
- minimum cost flow
- path length
- travel time
- finding the shortest path
- optimal solution
- special case
- search algorithm