Invention Grant
- Patent Title: Computer-implemented K-shortest path finding method
-
Application No.: US14556355Application Date: 2014-12-01
-
Publication No.: US09647927B2Publication Date: 2017-05-09
- Inventor: Bo Hu , Takahide Matsutsuka
- Applicant: FUJITSU LIMITED
- Applicant Address: JP Kawasaki
- Assignee: FUJITSU LIMITED
- Current Assignee: FUJITSU LIMITED
- Current Assignee Address: JP Kawasaki
- Agency: Staas & Halsey LLP
- Priority: EP14157957 20140305
- Main IPC: H04L12/721
- IPC: H04L12/721 ; G06Q10/04 ; H04L12/751

Abstract:
A computer-implemented method includes a principal process including performing a computational procedure in which the or each vertex preceding a particular vertex receives a notification that a computational procedure has been completed for the preceding vertex; and calculates new path lengths for the particular vertex by adding the length value attributed to the edge from the preceding vertex to the particular vertex to each of the recorded k shortest path lengths from the first vertex to the preceding vertex. A record of the k shortest path lengths calculated for the particular vertex is maintained. After the new path lengths have been calculated for the or each of the preceding vertices, a notification that the computational procedure has been completed for the particular vertex is issued. The computational procedure is performed with the source vertex as the first vertex and each vertex on a path from the source vertex to the destination vertex as the particular vertex.
Public/Granted literature
- US20150256442A1 COMPUTER-IMPLEMENTED K-SHORTEST PATH FINDING METHOD Public/Granted day:2015-09-10
Information query