[發(fā)明專利]一種圖上兩點間最短路徑查詢方法

有效

• 申請?zhí)枺?/td>: 201110421889.7
• 申請日: 2011-12-15
• 公開（公告）號: CN102521364A
• 公開（公告）日: 2012-06-27
• 發(fā)明（設(shè)計）人: 鄒磊;彭鵬;趙東巖;賈愛霞
• 申請（專利權(quán)）人: 北京大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 余長江

1.一種圖上兩點間最短路徑查詢方法，其步驟包括：

1)從圖上隨機抽取若干點作為支點，根據(jù)各支點間的最短路徑得出圖上每點的中間性估計值；

2)將中間性估計值大于設(shè)定值的點作為中心點及圖中各點到各中心點的最短路徑信息加入圖中各點的hop信息，這些中心點的集合記為Wb；

3)將圖去除Wb中各點后分割為若干小圖Si，1＜i≤m，m為小圖個數(shù)，并得到點割集Ws；

4)對于每個小圖Si根據(jù)枚舉出的任意兩點間最短路徑，得到該小圖Si內(nèi)的所有點的hop信息；

5)根據(jù)Wb中各點到Ws中各點的最短路徑得到不同小圖之間的點的hop信息；

6)根據(jù)圖中各點的hop信息，得到用戶輸入的兩查詢點之間的最短路徑。

2.如權(quán)利要求1所述的圖上兩點間最短路徑查詢方法，其特征在于，所述圖中各點的hop信息存儲為四元組<v，u，Dist_sp(v，u)，neighbor(v)|_u>，其中，v是大規(guī)模數(shù)據(jù)圖上的任意點，u是覆蓋v的一條最短路徑的中心點，Dist_sp(v，u)是u與v之間的距離，neighbor(v)|_u表示從v到u的最短路徑上v的鄰居，排序后形成一hop信息文件。

3.如權(quán)利要求2或1所述的圖上兩點間最短路徑查詢方法，其特征在于，所述hop信息文件可建立hop信息索引，將圖中各點的hop信息在hop文件的起始位置、長度存儲為三元組，該三元組為<v，pos，len>，其中v是該大規(guī)模圖中任意點，pos是每個點hop信息文件中起始位置，len是每個點hop信息文件長度。

4.如權(quán)利要求1所述的圖上兩點間最短路徑查詢方法，其特征在于，所述各支點間的最短路徑通過中間性算法得到，所述中間性公式為

Betweenness(u)=Σu1≠u≠u2∈Vσu1u2(u)σu1u2,]]>

其中，u₁和u₂分別表示圖上任意兩個點，V表示在一大規(guī)模圖中所有點所組成的集合，是u出現(xiàn)在不同的u₁和u₂之間的最短路徑總個數(shù)，是不同的u₁和u₂之間的最短路徑的總個數(shù)。

5.如權(quán)利要求1所述的圖上兩點間最短路徑查詢方法，其特征在于，所述分割方法為，使用METIS圖分割方法對所述大規(guī)模圖進行處理得到一邊割集合和小圖S₁，S₂，……，S_m，1＜i≤m，其中m為小圖的個數(shù)。