Multi-pairs shortest path finding method and system with sources selection

A system for solving a multiple-pairs shortest path problem using processing by a computer having storage means, the system comprising:

• means for reading graph data S on multiple vertices as search starting points from a storage area of the computer;
• means for reading graph data T on multiple vertices as search destinations from the storage area of the computer;
• means for selecting k vertices s1, s2, . . . , sk, k>1, based on close distance measure in order using Dijkstra method from the graph data S;
• means for deleting the k vertices from the graph data S;
• means for finding and storing, in the storage area, shortest path lengths from each of the selected k vertices to the graph data T;
• and
• repeating the means for selecting k vertices, deleting the k vertices, and finding and storing shortest path lengths until the graph data S becomes empty.

A computer program stored in a non-transitory computer-readable recording medium for solving a multiple-pairs shortest path problem, the program causing a computer having storage means to perform the functions of:

• reading graph data S on multiple vertices as search starting points from a storage area of the computer;
• reading graph data T on multiple vertices as search destinations from the storage area of the computer;
• selecting k vertices s1, s2, . . . , sk, k>1, based on close distance measure in order using Dijkstra method from the graph data S;
• deleting the k vertices from the graph data S;
• finding and storing, in the storage area, shortest path lengths from each of the selected k vertices to the graph data T;
• and
• repeating the functions selecting k vertices, deleting the k vertices, and finding and storing shortest path lengths until the graph data S becomes empty.