[發明專利]路徑計算順序決定方法、程序以及計算裝置

有效

• 申請號: 200980144964.0
• 申請日: 2009-11-18
• 公開（公告）號: CN102210128A
• 公開（公告）日: 2011-10-05
• 發明（設計）人: 杉園幸司;青木道宏;巖田英明
• 申請（專利權）人: 日本電信電話株式會社
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京三友知識產權代理有限公司 11127
• 代理人: 李輝;馬建軍

技術領域

本發明涉及路徑計算順序決定方法、程序以及計算裝置，特別涉及決定使用節點之間的已計算出的最短路徑來計算其他節點之間的最短路徑時的路徑計算順序的路徑計算順序決定方法、程序以及計算裝置。

背景技術

存在如下情況：網絡內的節點、連接節點之間的道路(路線)、網絡鏈接的鋪設狀況(拓撲)產生變化，數據可以通過此前無法通過的部位，或者相反，無法通過此前可以通過的部位。

在需要始終掌握從出發地(起點節點)到目的地(終點節點)的最短路徑的情況下，伴隨路線拓撲的變化，需要再次計算變化后的拓撲中的從出發地(起點節點)到目的地(終點節點)的最短路徑。

現有的最短路徑計算裝置使用表示變化后的拓撲的拓撲信息，再次計算連接各節點之間的全部最短路徑。在非專利文獻1中記載了使用拓撲信息來計算各節點之間的最短路徑的方法。

非專利文獻1：E.W.Dijkstra、「A?Note?on?Two?Problems?in?Connexion?with?Graphs」、1959年6月11日、Numerische?Mathematik?1，p269-271

發明內容

發明要解決的課題

在已經計算了某個連接節點之間的最短路徑的情況下，有時在該已計算出的節點之間的最短路徑和由此計算的其他節點之間的最短路徑之間存在共同的部分(以下稱為“共同部分”)。

在存在共同部分的情況下，能夠采用該共同部分作為由此計算的節點之間的最短路徑的計算結果的一部分。

特別地，在已計算出的節點之間的最短路徑中包括表示由此計算的從起點到終點的最短路徑的部分(以下稱為“部分路徑”)的情況下，該部分路徑是由此計算的最短路徑。

由已計算出的各節點之間的最短路徑構成的最短路徑組包括越多的部分路徑，使用該已計算出的最短路徑組的信息，越能夠縮短由此計算的節點之間的最短路徑的計算時間。

以往，著眼于這一點，即由已計算出的各節點之間的最短路徑構成的最短路徑組包括越多的部分路徑，使用已計算出的最短路徑組的信息，越能夠縮短由此計算的節點之間的最短路徑的計算時間，不存在縮短節點之間的最短路徑的計算時間的技術。

本發明的目的在于，提供以能夠縮短節點之間的最短路徑的計算時間的方式決定節點之間的最短路徑的計算順序的路徑計算順序決定方法、程序以及計算裝置。

用于解決課題的手段

本發明的路徑計算順序決定方法是計算裝置執行的路徑計算順序決定方法，該計算裝置針對由多個節點構成的網絡，使用節點之間的已計算出的最短路徑來計算其他節點之間的最短路徑，其特征在于，所述計算裝置具有存儲單元和計算單元，該存儲單元存儲最短路徑組信息和拓撲信息，所述最短路徑組信息通過多個節點和該多個節點中的各節點之間的路徑來表示起點節點相同且終點節點不同的各節點之間的已計算出的最短路徑，所述拓撲信息表示所述多個節點的拓撲，所述路徑計算順序決定方法包括計算步驟，在該計算步驟中，所述計算單元按照在所述最短路徑組信息表示的各節點之間的已計算出的最短路徑中位于特定節點下游的節點的數量從多到少的順序，選擇所述多個節點中與所述起點節點不同的每一個所述特定節點，每次選擇所述特定節點時，使用其他節點之間的已計算出的最短路徑和所述拓撲信息，計算以該選擇出的特定節點為起點且以所述多個節點中的其他各節點為終點的各節點之間的最短路徑。

本發明的程序用于使存儲有最短路徑組信息和拓撲信息的計算機針對由多個節點構成的網絡執行計算步驟，所述最短路徑組信息通過多個節點和該多個節點的各節點之間的路徑來表示起點節點相同且終點節點不同的各節點之間的已計算出的最短路徑，所述拓撲信息表示所述多個節點的拓撲，在所述計算步驟中，按照在所述最短路徑組信息表示的各節點之間的已計算出的最短路徑中位于特定節點下游的節點的數量從多到少的順序，選擇所述多個節點中與所述起點節點不同的每一個所述特定節點，每次選擇所述特定節點時，使用其他節點之間的已計算出的最短路徑和所述拓撲信息，計算以該選擇出的特定節點為起點且以所述多個節點中的其他各節點為終點的各節點之間的最短路徑。