  We present a new approach called GR (Graph Reduction) algorithm for searching
loop-less k-shortest paths (1st to k-th shortest paths) in a graph based on
graph reduction. Let a source vertex and a target vertex of k-shortest paths be
v_s and v_t respectively. First our approach computes shortest paths to every
vertex from v_s and v_t respectively, and reduce a graph to a subgraph that
contains all vertices and edges of loop-less k-shortest paths using the already
computed shortest paths, and apply an existing k-shortest path search algorithm
to the reduced graph. A graph can be reduced quickly after computing the
shortest paths using them, therefore a very efficient search can be achieved.
In an experiment using a hypercube graph which has 16384 vertices where k=128,
the number of vertices is reduced to about 1/22, and a variant of Dijkstra
algorithm for k-shortest path search were speeded up by about 365 times. We
implemented a fast k-shortest path variant of bidirectional Dijkstra algorithm
(k-biDij) which is the state-of-the-art algorithm and the fastest as long as we
know, GR outperforms k-biDij in dense scale-free graphs. However, k-biDij
outperforms GR in hypercube-shaped and sparse scale-free graphs, but even then
GR can also speed up it by 12.3 and 2.0 times respectively by precomputing
all-pairs shortest paths. We also show the graph reduction can be done in time
complexity O(m + n log n). We also introduce our improvements to k-biDij
simply.
