摘要 |
PROBLEM TO BE SOLVED: To provide a method and a system for solving at high speed, a shortest path problem from a plurality of start points to a plurality of end points.SOLUTION: As a first aspect, a method for solving a multi-pairs shortest path problem using processing by a computer having a storage means is provided, which includes the steps of: (A) reading graph data S on a plurality of vertices as search starting points from a storage area of the computer; (B) reading graph data T on a plurality of vertices as search targets from the storage area of the computer; (C) selecting k vertices s1, s2, ..., sk from the graph data S; (D) deleting the k vertices from the graph data S; (E) finding and storing, in the storage area, shortest path lengths from each of the selected k vertices to the graph data T; and (F) repeating the steps from (C) to (E) until the graph data S becomes empty. |