圖數(shù)據(jù)庫中查詢無權(quán)圖中兩點(diǎn)間最短路徑的方法及應(yīng)用

基本信息

申請?zhí)?/td> CN201810359289.4 申請日 -
公開（公告）號 CN108595603A 公開（公告）日 2021-07-02
申請公布號 CN108595603A 申請公布日 2021-07-02
分類號 G06F17/30 分類 計算；推算；計數(shù);
發(fā)明人 洪春濤;朱曉偉;王濤 申請（專利權(quán)）人 深圳神圖科技有限公司
代理機(jī)構(gòu) 北京睿邦知識產(chǎn)權(quán)代理事務(wù)所（普通合伙） 代理人 徐丁峰
地址 100080 北京市海淀區(qū)海淀大街3號1幢801室-810L-027
法律狀態(tài) -

摘要

摘要 圖數(shù)據(jù)庫中用于查詢無權(quán)圖中兩點(diǎn)間最短路徑的長度的方法，假設(shè)給定的圖為G（V,E），需要查詢點(diǎn)a到點(diǎn)b的最短路徑，限定的最長跳數(shù)為K，則最短路徑查詢方法包括：（1）比較a側(cè)的潮頭和b側(cè)的潮頭的大??；（2）選擇兩側(cè)的“潮頭”中的元素數(shù)目較小的一側(cè)，以及得到該側(cè)的新潮頭；（3）重復(fù)上述步驟（1）和（2）直到：查找到一個潮頭節(jié)點(diǎn)y，它既是a的潮頭節(jié)點(diǎn)，又是b的潮頭節(jié)點(diǎn)，此時確定找到最短路徑，或者達(dá)到其它預(yù)定的終止條件；（4）若確定找到最短路徑，則確定a，b兩點(diǎn)之間最短路徑的長度。本發(fā)明利用雙向搜索，以及基于潮頭大小的方向選擇，可以大大減少搜索范圍，從而可以在大規(guī)模的圖上高效的執(zhí)行兩點(diǎn)間最短路徑查詢。