TD-H2H：時序圖上的最短路徑查詢

李新玲，王一舒，袁野，谷香，王國仁

1.東北大學 計算機科學與工程學院，沈陽110167

2.北京理工大學 計算機學院，北京100081

圖數據已廣泛用于社交媒體營銷、知識發現、交通網絡以及移動網絡分析等場景[1]。圖中的最短路徑查詢是一個已經被廣泛研究的基本問題，是許多應用的基礎，例如路徑規劃、信息與疾病傳播以及生物學中的代謝途徑分析等[2]。道路網絡中的路徑規劃問題是基于位置服務的重要研究[3]，合理的規劃方案能夠幫助人們更有預見性地旅行。為回答該問題，現有研究通常將道路網絡建模為靜態圖，并將給定節點對在圖中的最短路徑作為規劃結果返回，其中最短路徑是指邊權重和最小的路徑，即總距離最短的路徑。但是，現實生活中，同一條道路，在不同的出發時間下，所需的通過時間通常是不同的，例如，一條道路在早晚高峰時通過往往會花費更多的時間。因此，距離最短的路徑并不完全等于旅行時間最短的路徑。顯然對于用戶來說，旅行時間最短的路徑才是更合理的路徑規劃結果。

由于需要考慮時間的影響，交通網絡是最適合建模為時序圖的網絡之一[4]。很多的交通管理系統能夠向用戶提供實時的交通信息，這些交通系統所管理的道路網絡都可以被刻畫為大規模的圖數據模型。在這些模型中，通過一條邊（道路）的代價不是一成不變的，而是會隨著時間的變化而變化[5]。因此，本文將道路網絡建模為時序圖GT(V,E,F)，GT邊上的權重fe(t)∈F與時間信息相關聯，是以出發時間t為自變量的函數，表示出發時間為t時通過邊e∈E所需的時間。文獻[6]已經證明了時序最短路徑查詢問題在具有先進先出屬性的時序圖上是多項式可解的。其中FIFO 屬性是指：對于任意出發時間t1＜t2，有t1+fe(t1)＜t2+fe(t2)，即如果汽車A與B都需要行駛過道路L，并且A先于B進入L，那么一定也是A先于B離開L。本文假設時序圖中每條邊上的權重函數都具有FIFO屬性。

道路網絡的規模很大，每一個節點都只能通過它的入邊鄰居到達[7]。建模為時序圖后，邊上的權值從常數變為了時間函數，相比靜態圖，時序圖的結構要復雜、龐大得多。因此，如果源節點與目的節點間的距離很遠，使用非索引方法進行時序最短路徑查詢時，通常需要幾十秒才能得出查詢結果，并不能在實際生活中應用。為提高查詢效率，本文基于樹分解[8]的概念構建了TD-H2H（time dependent-hierarchical 2-hop）索引。樹分解是一種將圖轉變為樹結構的操作，也可用于表示分解操作后得到的樹結構TG。基于圖的樹分解思想，可以將規模大且難解的問題轉化為規模小且易解的子問題。樹寬是樹分解的重要性質之一，如果圖的樹寬被常數限制，那么圖上許多棘手的問題都可以在多項式時間甚至線性時間內解決[9]。給定圖G，節點u和v在G內的點割集是指u和v間所有路徑一定經過的節點的集合。任意兩個節點間的點割集都不是唯一的，且索引的大小與點割集內的節點數量成正比，查詢時間的長短與索引的大小成正比。確定的點割集越小，索引就越小，查詢速度越快。基于樹分解TG可以為G確定任意一對節點間的點割集，且每個點割集的大小都以TG的樹寬為界。又因為道路網絡可以分解為低樹寬的樹分解[10]，所以基于樹分解可以為圖中的節點對確定較小的點割集。綜上所述，為了加速求解時序道路網絡上的最短路徑查詢問題，本文設計了時序樹分解算法，通過該算法可以獲得具有較小樹寬的樹分解TGt，根據TGt獲得以樹寬為界的點割集C，根據C來創建TD-H2H索引以加速查詢，最后基于TD-H2H設計了高效的最短路徑查詢算法TD-OAI（time dependentout edge and in edge）。

本文的主要貢獻如下：

（1）基于傳統的樹分解方法提出了時序樹分解算法。時序樹分解中，使用時序節點消除操作構造樹節點，每個樹節點都由多個圖節點組成（第3章）。

（2）基于時序樹分解提出了索引TD-H2H，TDH2H由兩類最短旅行時間函數表組成，即out旅行時間表與in旅行時間表。使用樹分解能夠加速索引的構建過程，文中給出了詳細的構建算法（第4章）。

（3）基于TD-H2H設計了高效的最短路徑查詢算法TD-OAI，TD-OAI 根據樹分解中的節點訪問最短旅行時間函數表中的元素，可以很大程度地提高最短路徑查詢速度（第5章）。

（4）在真實數據集上進行了對比實驗，實驗結果證明了本文算法的有效性，且在查詢效率方面優于現有的算法（第6章）。

1 相關工作

樹分解最初由文獻[8]提出，給定圖G,樹分解是指對G中的節點集進行劃分后生成的一棵分解樹TG，TG中的節點與G中的節點子集一一對應。通過研究樹分解的結構信息可以加快圖中某些問題的計算速度。基于圖G可以生成多個樹寬不同的樹分解，每個樹分解的樹寬等于樹分解中包含最多圖節點的樹節點中圖節點的數量減1，其中具有最小樹寬的樹分解為G的最優樹分解。圖的樹寬和樹分解的引入給算法的分析和設計帶來了一些新的思路。某些NP問題，若將其限定在有限樹寬的圖中，則其求解是可行的[11]。現有計算最優樹分解的技術只能用于處理小圖（節點數量小于1 000的圖）[12]。此外，現有的樹分解算法均用于計算靜態圖無向圖的樹分解，無法直接處理時序有向圖。由于最優樹分解的計算難度大，本文通過改進對靜態無向圖進行樹分解的次優方法[13]來計算時序有向圖的樹分解，該算法不保證以有界近似比計算樹寬。本文的索引構建和查詢算法的時間復雜度都是樹寬的多項式且道路網絡可以分解為具有低樹寬的樹分解[10]，因此，次優的樹分解算法適用于現實中大型道路網絡中的路徑規劃問題。

靜態圖上的最短路徑查詢方法可以分為非索引方法與索引方法兩類，其中經典的非索引方法有Dijkstra方法、A*方法以及Floyd方法。Dijkstra[14]是經典的單源最短路徑查詢算法，查詢過程中需要進行多次迭代運算，每次迭代從候選集中選擇與源節點距離最短的節點作為訪問節點，直至候選集為空或候選集內不存在需要計算最短路徑的節點。Dijkstra的缺點為查詢效率低下，因為該方法不知道目標節點的位置，只能向所有可能的方向擴展節點，直到發現目標節點為止。為了克服Dijkstra算法效率低的缺點，文獻[15]提出了A*算法，A*算法[15]是改進版的Dijkstra 算法，在Dijkstra 的基礎上，使用啟發式方法估計最短路徑的距離，在保證最優性的同時，加入了目標節點的信息，提高了搜索效率。Floyd 算法[16]是經典的多源最短路徑查詢算法，可用于計算圖中所有節點對間的最短距離。道路網絡的規模很大，上述三種非索引算法通常需要數十秒才能回答大型道路網絡上的查詢，查詢速度不能滿足實際應用。因此，為了提高查詢速度，產生了許多基于索引的查詢方法，CH（contraction hierarchies）[17]是基于層次的索引方法，通過為圖中每個節點分配等級確定節點的層次，基于層次預先計算節點與子集中節點間的最短距離，查詢時直接訪問以加快查詢速度。HL（hierarchical hub labelings）[18]是基于跳的索引方法，為每個節點分配2跳標簽，查詢時只需要訪問源節點與目的節點標簽內的公共節點。H2H（hierarchical 2-hop）[10]是最新的基于索引的最短路徑查詢方法，彌補了上述兩種索引算法的缺點，能夠根據節點的層次選擇該節點的局部標簽進行最短距離查詢，進一步加快了查詢速度。

時序道路網絡由文獻[19]第一次提出，時序道路網絡即將道路網絡建模為時序圖，與邊上權值是固定的靜態圖相比，時序圖邊上的權值是動態的，會根據時間屬性產生相應的變化。道路網絡是最典型的時序網絡，考慮到早晚高峰、交通堵塞等情況，在不同時間，通過同一條道路所需的旅行時間也是不同的。文獻[6]證明了時序道路網絡上的最短路徑查詢在FIFO網絡中是多項式可解的。文獻[20]證明了不具有先進先出屬性的時序圖上的最短路徑查詢問題是NP難的。文獻[21]將Dijkstra推廣到具有隱式先進先出屬性的時序圖中。A*算法[15]被擴展為A*-like[22]后可用于時序路網上最短路徑查詢。CH[17]是靜態道路網絡中的層次加速技術，TCH（time dependent contraction hierarchies）[23]為CH 的改進版，可以用于時序路網中最短路徑的查詢。高度平衡的樹結構索引TD-G-tree[24]是最新回答時序道路網絡上最短路徑查詢的索引方法，雖然與TCH[23]相比TD-G-tree[24]的索引需要占據更多內存，索引構建時間也更長，但在查詢速度方面有了很大的提升。本文基于樹分解的概念，提出了可應用于時序圖的時序樹分解算法，并在此基礎上提出了時序索引TD-H2H，該索引可以加快時序道路網絡上的最短路徑查詢，實驗部分表明了其查詢效率優于索引TD-G-tree[24]。

2 問題定義

一般來說，道路網絡上的通行速度和出發時間有關，在不同的時間通過同一條道路，需要的時間可能也是不同的。因此，為了更準確地回答道路網絡上的最短路徑問題，本文將道路網絡建模為有向時序圖GT(V,E,F)，如圖1 所示，使用n=|V|以及m=|E|表示GT內的節點數和邊數。對于GT內的每個節點v∈V，使用dout(v)表示節點v的出度，din(v)表示節點v的入度。GT邊上的權重由函數表示，該函數使用時間變量t作為自變量，稱為時間函數。給定邊e=＜u,v>∈E，其對應的時間函數fe(t)∈F表示在時刻t從節點u∈V出發，通過邊e=＜u,v>到達節點v∈V所需的時間是fe(t)。本文使用分段線性函數表示時間函數，S表示時間函數的段數，I表示插值點數。段數為S的時間函數需要I=S+1 個插值點來表示，如圖2所示，兩個段數S=2 的時間函數，需要使用I=3 個插值點來表示，分別為{(0,10),(30,20),(60,20)} 與{(0,15),(35,25),(60,40)}。后文中將通過時序圖中的邊以及路徑所需要的時間統稱為旅行時間。

圖1 時序圖GTFig.1 Time-dependent graph GT

在遍歷時序圖GT時，每個被訪問的節點v都存在一到達時間Arr(v) 與出發時間Dep(v) 。給定邊e=＜u,v>，有Arr(v)=Dep(u)+fe(Dep(u))，Dep(v)=Arr(v)，即節點v的到達時間等于節點u的出發時間與通過邊e=＜u,v>所需的旅行時間的和，v的出發時間等于其到達時間。基于節點的到達時間與出發時間可以對時序圖中路徑的旅行時間函數與最短旅行時間函數進行定義，具體定義如下：

定義1（路徑的旅行時間函數）給定時序圖GT，邊e=＜u,v>。令出發時間為t，即Dep(u)=t。則e的到達時間函數為Arre(t)=Arr(v)=t+fe(t)；路徑P=＜e1,e2,…,eh-1,eh>的到達時間函數Arrp(t)為Arrp(t)=Arreh(Arreh-1(…(Arre1(t))…))；進而，路徑p的旅行時間函數為Trvp(t)=Arrp(t)-t。

例1圖1為時序圖GT，圖2為GT中邊＜2,1>與邊＜1,6>上的時間函數圖。取Dep(2)=10，根據定義1，節點1 的到達時間以及出發時間分別為Arr(1)=Dep(1)=Dep(2)+f＜2,1>(Dep(2))，邊＜2,1>的到達時間Arr＜2,1>(10)=10+f＜2,1>(10)=Arr(1) 。對于路徑p={2,1,6}，給定Dep(2)=0，p的旅行時間為Trvp(0)=Arr＜1,6>(Arr＜2,1>(0))=Arr＜1,6>(10)。

圖2 時間函數Fig.2 Time functions

定義2（最短旅行時間函數）給定時序圖GT。出發時間為t時，從源節點s∈V到目的節點d∈V的最短旅行時間函數記為Trv*(s,d,t)，表示在t時刻從u出發到達v所需的最短時間。

時序圖中將節點間旅行時間最短的路徑定義為最短路徑。時序最短路徑查詢的定義如下：

定義3（時序最短路徑查詢）給定時序圖GT(V,E,F)，源節點s，目的節點d，以及出發時間t，時序最短路徑查詢表示為q(s,d,t)，返回出發時間為t時具有最短旅行時間Trv*(s,d,t)的路徑ps,d*。

例2如圖1 所示，GT中節點4、6 之間的路徑有{4,7,6}、{4,5,6}以及{4,8,5,6}。給定查詢q(4,6,10)，時序最短路徑查詢將返回在10 時刻出發時，節點4與節點6間具有最短旅行時間的最短路徑。

3 時序樹分解

樹分解[8]將圖分解為樹形結構，通過研究樹分解的結構信息可以加快圖中某些問題計算的速度。因此，本章在靜態圖上的樹分解方法的基礎上，提出了時序樹分解算法。

3.1 時序樹分解定義

時序樹分解的定義如下：

定義4（時序樹分解）時序圖GT(V,E,F)的時序樹分解表示為有根樹，其中每個節點X∈V()是集合V的子集（即X?V），使用X(r)表示TGt的根，滿足如下條件：

（1）GT的每個節點至少出現在的一個包內；

（2）對于E中的每條邊e,e上的兩個節點至少同時出現在中的一個包內；

（3）?v∈V，{X|v∈X}組成內一個連接子樹T(v)，X(v)表示T(v)在內的根，將v稱為X(v)的包頭節點，X(v)內除v以外的節點稱為包內節點。

（4）?v∈V，根據時序圖GT的結構在X(v)內保存包頭節點v與包內節點u間的邊以及邊上的時間函數。

為了便于表述，后續將使用“節點”表示時序圖GT中的節點，使用“包”表示時序樹分解中的節點。

樹分解有兩個屬性，分別是樹寬和樹高：樹寬=max{|X||X∈}-1；樹高h(TGt)=max{h(X)|X∈}，其中h(X)是指包X在內的高度，即X到TG的根X(r)的距離。給定圖GT，根據定義4可以獲得多個樹寬不同的時序樹分解。假設具有最小樹寬的樹分解為Tmin，則有GT的樹寬w(GT)=w(Tmin)。將GT具有最小樹寬的樹分解Tmin定義為GT的最優樹分解。判斷GT的樹寬是否大于給定值的問題是NP完全的[9]。現有計算最優樹分解的技術只能用于處理小圖（節點數量小于1 000圖）[12]。因此，為了能對時序圖進行樹分解操作，且獲得較小的樹寬，本文將改進文獻[13]提出的對靜態圖進行樹分解的次優方法。3.2節將給出算法細節以及詳細的算法說明。

3.2 時序樹分解構建

現有的樹分解算法均用于計算靜態無向圖的樹分解，無法直接對時序有向圖進行處理。時序樹分解需要計算并保存時序圖邊上的權值（時間函數），在給出時序樹分解的算法之前，首先介紹兩個處理時間函數方法，Com()方法[24]與Min()方法[24]，給定兩個時間函數fuw和fwv，兩個函數的插值點個數分別為Iuw與Iwv，Com()方法返回將這兩個函數復合后得到的新的時間函數fuv，即fuv=Com(fuw,fwv)，Com()方法的時間復雜度為α=O(Iuw+Iwv)；與作用于三個節點間的兩個時間函數上的Com()方法不同，Min()方法作用于同一對節點間的兩個時間函數上，給定時間函數fuv和,fuv的插值點個數為Iuv,的插值點個數為，且兩個函數的交叉點個數為C，Min()方法返回在所有出發時間t下旅行時間都較小的新的時間函數，即=Min(fuv,)，Min()方法的時間復雜度為β=O(Iuv++C)。

構建時序樹分解的方法包括兩個步驟：第一步是創建包，給定時序圖GT并運行|V(G)|次迭代，為了生成樹寬盡可能小的樹分解，每次迭代又由兩個小步驟組成。步驟1是每次迭代都選擇GT中度數最小的節點u，并且使用u和u在GT中的所有鄰居N(u,G) 創建包X(u)，其中u為X(u) 的包頭節點，N(u,G)內的節點均為X(u)的包內節點。步驟2為在u的每對未連接的鄰居節點對間加入邊，并從G中刪除節點u以及所有與u相連的邊。步驟2 又可以被稱為時序節點消除操作，具體過程如算法1所示。

算法1時序節點消除算法

輸入：GT(V,E,F)，v∈V。

輸出：GT?v。

給定時序圖GT以及節點v，算法1訪問所有與v相連的邊，如果v在GT內有邊＜u,v>和＜v,w>（1行），使用Com()方法構建u和w間以v為中轉節點的邊＜u,w>以及時間函數=Com(fuv,fvw)（2 行），如果GT中u和w間沒有邊（3行），插入邊＜u,w>并將邊權重賦值為（4行），反之，如果u和w間有邊使用Min()方法更新邊權重（5～6 行），從H中刪除節點v以及所有與v相連的邊（8 行），最后返回完成時序節點消除操作的圖GT?v（9行）。

算法1 的時間復雜度為O(dout(v)×din(v)×(α+β))，即O(w2×(α+β))，其中dout(v)與din(v)分別為節點v在圖GT內的出度和入度，α與β分別為Com()與Min()方法的時間復雜度，w為樹寬。

根據上述的算法過程可以得出一個結論，給定時序圖GT(V,E,F) 以及GT?v=(Vd,Ed,Fd)，那么Vd?V，并且對于Vd中任意一對節點u和v，這對節點間的最短旅行時間等于V中u和v間的最短旅行時間，本文中將具有這種特性的圖叫作派生子圖，即是GT的派生子圖。

創建的第二步是連接包。連接過程所遵行的準則是：若節點v是節點u第一個被移除的鄰居，則將X(v)設置為X(u)在TG內的父包。與靜態樹分解相同，時序樹分解也有創建與連接包兩個過程。不同的是使用算法1 來創建包，且的每個包X(v)中不僅保存節點，如果存在邊＜v,u>，還需要保存＜v,u>以及時間函數fvu(t)。時序樹分解的具體過程如算法2所示。

算法2時序樹分解算法

輸入：GT(V,E,F)。

輸出：。

給定時序圖GT。算法2 首先將賦值為空（1行）。接著進行創建包的操作（2～14行），每次選擇GT中度數最小的節點v（3 行），將節點v設置為包X(v)的包頭節點（4 行），遍歷v在GT中的每個鄰居u（5行），如果GT中存在邊＜v,u>（6 行），將節點u加入到包X(v)的out鄰居集合中并且保存邊＜v,u>上的時序函數（7～8行）。同理，如果GT中存在邊＜u,v>，將節點u加入到包X(v)的in鄰居集合中并且保存邊＜u,v>上的時序函數（9～11）行。使用算法1從GT中消除v（12 行），之后記錄包X(v)的創建次序i（13行）。所有的包都創建完畢后，將已創建的包連接起來以形成樹結構（15～19 行）。最后返回生成的時序樹分解（20行）。

算法2的時間復雜度為O(n×(w+w2))=O(n×w2)，其中O(w2)為時序節點消除操作的時間復雜度。內的樹節點數等于GT內的圖節點數n，每個樹節點內包含的邊數上限為2(w-1)。因此，算法2 的空間復雜度為O(n×2(w-1)×I)=O(n×w×I)，其中I為時序圖GT中時間函數的平均插值點數。

例3圖3 展示了圖1 中時序圖GT的時序樹分解，中每個包內陰影里的節點是包頭節點，其余節點是包內節點，每個包內的箭頭表明了包內節點與包頭節點的關系。在構建時，首先選擇GT中度數最小的節點1，1的鄰居集為{2,6}，其中節點2為節點1的in鄰居，將節點2添加到節點1的in鄰居集合中，保存時序函數f21，同理將節點6添加到節點1的out鄰居集合中并且保存時間函數f16。GT中存在邊＜2,1>與＜1,6>，從節點2 出發可以通過節點1 到達節點6，因此對節點1進行時序節點消除時，需要在GT中插入邊＜2,6>，邊上的時間函數通過Com()操作得到f26=Com(f21,f16)。表1 展示了中所有包的鄰居集，除了樹分解的根X(8)的兩個鄰居集都為空之外，其余的包至少有一個in鄰居集或out鄰居集。

圖3 時序樹分解TGtFig.3 Time-dependent tree decomposition TGt

表1 的鄰居集Table 1 Neighbor sets of

表1 的鄰居集Table 1 Neighbor sets of

4 時序索引

4.1 TD-H2H

現實生活中，道路網絡的規模很大，建模為時序圖后其結構也更為復雜，直接求解大規模時序圖上的最短路徑問題難度很高，且其效率不足以支持實際的應用。因此，索引是必須的。為了理解TD-H2H索引的原理，首先需要明確點割集的概念。

定義5（點割集）給定時序圖GT(V,E,F)，節點集C?V，從圖G中刪除C會將圖GT劃分為多個連接子圖，如果節點u和v存在于不同的子圖中，那么C被稱為u和v的點割集。

給定源節點s和目的節點d間的點割集C，s與d間的所有路徑都至少會通過C中的一個節點c[10]。s與d間的點割集并不是唯一的，因此，如果能夠提前確定s和d間一個較小的點割集C，并且預計算并保存從s到c的最短旅行時間函數，以及由c到d的最短旅行時間函數，查詢時直接調用已保存的時間函數可以大大提高時序最短路徑的查詢效率。現在需要考慮的問題是，給定節點u和v后，如何確定節點間的點割集，并且保證這個點割集的大小是可以接受的。文獻[25]給出的樹分解的點割集性質可以回答此問題。

性質1[25]給定時序圖GT(V,E,F)的時序樹分解，以及V中任意兩個節點u和v，假設X(u)不是X(v)在內的祖先或后代，并且令X是X(u)和X(v)在內的最小公共祖先，則X內的節點是u和v在GT內的一個點割集。

首先，算法2可以將路網轉換為具有低樹寬的樹分解[10]，由性質1 可知將圖轉換為樹分解結構后，根據該樹結構可以確定節點間的點割集并且所有點割集的大小都小于等于樹寬。基于此，本文將道路網絡建模為時序圖后，生成該圖的時序樹分解，并在該樹分解的基礎上構建TD-H2H索引。

祖先數組可以加快索引的構建過程，是構建TDH2H索引的基石。給定時序圖GT(V,E,F)的時序樹分解TGt，對于中的每個包X(v)，都存在從根節點X(r)到節點X(v)的路徑{X(w1),X(w2),…,X(wl)}，其中X(w1)是X(r),X(wl)是X(v)。使用X(v).anc表示X(v)的祖先數組，即X(v).anc={w1,w2,…,wl}，X(v).anc[i]表示數組中的第i個元素(1 ≤i≤l)。祖先數組中各個元素必須按包頭節點在樹分解中由上至下的順序存放，保證排在前面的元素是后面元素在內的祖先。根節點X(r)的祖先數組只有r一個元素，其他包的祖先數組至少有兩個元素，即r和v。

給定時序樹分解以及每個包X(v)∈V()在內的祖先數組X(v).anc，本文會為每個X(v)計算并保存旅行時間函數表X(v).trv作為TD-H2H 索引，該索引使用哈希表來存儲。根據算法2，?X(v)∈V()中都有兩類邊，分別是out邊與in邊。相應的，X(v)的旅行時間函數表X(v).trv也分為兩類，分別是X(v).trvout與X(v).trvin表。如果GT內存在從包頭節點v到X(v).anc中節點w的路徑，則X(v).trvout中保存從節點v到節點w的最短旅行時間函數X(v).trvout[w]=Trvvw*(t)。如果GT內存在從X(v).anc中節點w到包頭節點v的路徑，那么在X(v).trvin中保存從節點w到節點v的最短旅行時間函數X(v).trvin[w]=Trvwv*(t)。給定時序樹分解以及每個包X(v)∈V()在內的祖先數組，在為X(v)計算旅行時間表之前，需要為X(v)計算并保存位置數組X(v).pos。與旅行時間函數表相同，位置數組也分為兩類，分別為X(v).posout和X(v).posin數組。位置數組顧名思義是由包X(v)的包內節點在X(v).anc中的位置組成的數組，X(v).posout中保存X(v)的out鄰居集中的節點在X(v).anc中的位置，X(v).posin中保存X(v)的in鄰居集中的節點在X(v).anc中的位置。TD-H2H的具體構建過程將在4.2節中詳述。在構建的位置數組時默認使用了樹分解的一個性質，即對于內的每個包X(v)來說，若u為X(v)的包內節點，那么X(u)是X(v)在內的祖先，具體內容如下：

性質2[10]給定時序圖GT(V,E,F)，其樹分解以及任意包X(u)∈，對于任意節點v∈X(u)/u，X(v)是X(u)在內的祖先。

除祖先數組的構建需要性質2的支持外，旅行時間函數表的構建也與性質2 有關，前文已經說明了TD-H2H 需要提前存儲源節點s與點割集C中節點以及點割集C中節點與目的節點d間的最短旅行時間函數。根據性質1，X(s)與X(d)的在內最小公共祖先X中的節點就是s與d間的點割集。由此可以得出：對GT中任一節點u與其他節點v，如果X(u)不是X(v)在內的祖先或后代，那么u與v間的點割集一定是X(u)的祖先，且根據性質2，以X(u)的包內節點v為包頭節點的X(v)一定是X(u)的祖先。因此，只要提前保存好X(u) 的兩個旅行時間函數表X(u).trvout與X(u).trvin，就已經保存了節點u與點割集C中每個節點c間的最短旅行時間函數。如果X(u)是X(v)在內的祖先或后代，不需要計算u和v間的點割集，根據已保存的旅行時間函數表可以直接進行最短旅行時間的計算。因為如果X(u)是X(v)的祖先，那么從u到v的最短旅行時間函數已經提前保存在節點v的in旅行時間表中，即X(v).trvin[u]；如果X(v)是X(u)的祖先，那么從u到v的最短旅行時間函數已經提前保存在節點u的out旅行時間表中，X(u).trvout[v]。綜上所述，計算節點u到v的最短路徑時只需要訪問已經提前存儲的u的out旅行時間表與v的in旅行時間表，又因為旅行時間表的大小一定小于等于樹寬，并且道路網絡可以分解為具有低樹寬的樹分解[10]，所以，基于時序樹分解構建的索引TDH2H可以大大加快時序圖上的最短路徑查詢速度。

例4如圖3 所示，X(3)與X(5)的最小公共祖先是X(4)={8,7,6,4}，且在圖1的GT中，C={8,7,6,4}是節點3 與5 間的點割集。X(9)={4,2,9}，而且X(4)和X(2)均為X(9)在的祖先。表2展示了圖3中的祖先數組與位置數組。X(3)={4,2,9,3}的祖先數組為X(3).anc={8,7,6,4,2,9,3}，節點8是X(3).anc中其他所有節點在中的祖先，節點7是X(3).anc中除了節點8 外所有節點在中的祖先，且X(3)?X(3).anc。X(3).posin={4,6}，說明X(3)的in鄰居集中的第一個元素4在X(3).anc中的第4 個位置，in鄰居集中的第2個元素9在X(3).anc中的第6 個位置；同理可得X(3).posout={5}說明X(3)的out鄰居集中的唯一一個元素2在X(3).anc中的第5 個位置。如表1 所示，X(4)的out鄰居集為空，因此，在表2中X(4).posout中的元素也為空。表3展示了圖3中的旅行時間表，對于中的任意節點X(v)，X(v)的in和out旅行時間表中至少會保存到自身包頭節點v的旅行時間函數，本文中將到自身包頭節點的旅行時間函數值設置為0。如圖1 中的GT所示，X(9).anc={8,7,6,4,2,9}中除了節點9外，其余節點在GT都不存在到達節點9的路徑，但是從節點9 出發可以到達X(9).anc中的每個節點。因此，在X(9)的in旅行時間函數表中僅保存了到自身的旅行時間函數，out旅行時間函數表中保存9 到所有祖先節點的最短旅行時間函數。因為X(8)為的根，所以其in和out旅行時間表中都只保存了到自身的旅行時間函數。

表2 的祖先數組與位置數組Table 2 Ancestor and position arrays of

表2 的祖先數組與位置數組Table 2 Ancestor and position arrays of

表3 的旅行時間表Table 3 Travel time tables of

表3 的旅行時間表Table 3 Travel time tables of

4.2 索引構建

本節給出索引TD-H2H的構建細節，并詳細說明如何基于時序樹分解的性質以及位置數組設計高效的索引構建算法。

給定時序圖GT(V,E,F)，在構建時序樹分解時使用算法1 進行時序節點消除，且在內會保存包頭節點與包內節點的時間函數。因此，對于V中每個節點v，X(v).anc={w1,w2,w3} 中的節點和X(w1)、X(w2)以及X(w3)內的邊組成的圖G(v)T(Vd,Ed,Fd)是GT的派生子圖，即Vd?V，并且對于Vd中任意一對節點u和w，這對節點間的最短旅行時間等于V中u和w間的最短旅行時間。如果X(u)是X(v)在內的祖先，那么G(u)T是G(v)T的子圖。

例5根據圖3 的時序樹分解，可以得到圖4中的兩個派生子圖G(1)與G(2)。其中，G(2)中的節點與X(2).anc中的節點一致，G(2) 中的邊與包X(2)、X(4)、X(6)以及X(7)中的邊一致。因為X(2)是X(1)的祖先，相對的G(2)是G(1)的子圖。

圖4 派生子圖G(v)Fig.4 Derive subgraph G(v)

基于時序樹分解的派生子圖性質有如下結論：

給定時序樹分解以及內包X(v)，對于任意1 ≤i＜|X(v).anc|，1 ≤j≤|X(v).outN|，1 ≤k≤|X(v).inN|(X(v).outN為包頭節點v在包X(v)內的out鄰居集，X(v).inN為in鄰居集）有：

上述結論說明在求解X(v)的out旅行時間表時，需要逐一訪問X(v).anc中的節點w。如果X(v)的out鄰居集中有能到達w的節點u，則通過Com()方法計算出v與w間的旅行時間函數Trvv,w(t)。如果存在不只一個節點v可以到達w，需要使用Com()方法計算出所有v與w間的旅行時間函數Trvv,w(t)。將計算出的時間函數Trvv,w(t)依次帶入到Min()方法中，得到從v到w的最短旅行時間函數Trvv,w(t)*。同理可得X(v)的in旅行時間表。相關證明如下：

證明因為GT(v)是包含X(v).anc中全部節點的圖，且GT(v)是GT的派生子圖，所以GT中從v到X(v).anc[i]的最短旅行時間函數等于GT(v)中從v到X(v).anc[i]的最短旅行時間函數。又因為X(v)/v是節點v在GT(v)中鄰居的集合，從節點v到X(v).anc中的任何一個節點間的路徑都至少會經過v的一個鄰居。因此，基于樹分解中每個包內保存的圖節點以及時間函數可以計算出正確的旅行時間函數表。

綜上所述，給定時序圖GT以及其樹分解，對于內的每個包X(v)，計算旅行時間表時都隱式構建了圖G(v)T，進而在G(v)T上計算旅行時間表。當X(u)是X(v)在內的祖先時，G(u)T是G(v)T的子圖。因此，如果在構建中每個包的旅行時間表時采用由上至下的遍歷方式，在創建X(v)的旅行時間表時可以重用已計算完成的X(u)的索引信息。

對于任意1 ≤i＜|X(v).anc|以及1 ≤j≤|X(v).outN|，如果通過X(v).outN[j] 可以到達X(v).anc[i]，計算X(v).trvout[X(v).anc[i]]時，需要已知Trv*(X(v).outN[j],X(v).anc[i])的值，考慮如下情況：

（1）X(v).posout[j]>i，即X(v).outN[j]在X(v).anc中排在X(v).anc[i]的后面，在這種情況下，X(X(v).anc[i])是X(X(v).outN[j])在內的祖先，有：

（2）X(v).posout[j]≤i，即X(v).outN[j]在X(v).anc中排在X(v).anc[i]的前面，在這種情況下，X(X(v).outN[j])是X(X(v).anc[i])在內的祖先，有：

X(X(v).outN[j])與X(X(v).anc[i])都是X(v) 的祖先并且采用由上至下的方式計算內每個包的旅行時間表，因此，在計算X(v) 的旅行時間表時，X(X(v).outN[j])與X(X(v).anc[i])的旅行時間表都已經計算完成，計算X(v).trvout時可以直接調用以加速索引的構建過程。同理可得，對于任意1 ≤i＜|X(v).anc|以及1 ≤k≤|X(v).inN|，如果X(v).anc[i]可以到達X(v).inN[k]，計算X(v).trvin[X(v).anc[i]]時，需要已知Trv*(X(v).anc[i]，X(v).inN[k])的值，考慮如下兩種情況：

（1）X(v).posin[k]>i，即X(v).inN[k]在X(v).anc中排在X(v).anc[i]的后面，在這種情況下，X(X(v).anc[i])是X(X(v).inN[k])在內的祖先，有：

（2）X(v).posin[k]≤i，即X(v).inN[k]在X(v).anc中排在X(v).anc[i]的前面，在這種情況下，X(X(v).inN[k])是X(X(v).anc[i])在內的祖先，有：

TD-H2H索引的構建原理與方式如上文所述，下文分別給出創建out旅行時間表的算法GetOutTrv與創建TD-H2H 索引的算法，創建in旅行時間表的算法GetInTrv與GetOutTrv相似，不再具體說明。

算法3GetOutTrv

輸入:、v。

輸出:X(v).trvout。

算法3 生成X(v)的trvout旅行時間表。依次遍歷祖先數組X(v).anc中的每個節點（1 行），將每個X(v).trvout[X(v).anc[i]]的初值賦值為任何時間出發旅行時間都為無窮大的fmax函數（2 行），訪問X(v)在out鄰居集中的元素X(v).outN[j]，依次計算X(v).trvout[X(v).anc[i]]（3～13行）。將節點到本身的旅行時間函數設置為旅行時間為0的fmin函數（15 行），最后返回節點v的trvout表（17行）。

算法3 在3～14 行的時間復雜度為O(w×(α+β))，且總的循環次數以的樹高h為上界。因此，算法3的時間復雜度為O(h×w×(α+β))。

算法4創建TD-H2H索引

輸入：GT(V,E,F)。

輸出：TD-H2H。

算法4 首先調用算法1 構建時序樹分解（1行），接著由上至下逐一訪問中的包X(v)（2～11行）。分別計算X(v)的位置數組X(v).posout（3～5行）與X(v).posin（6～8 行）。接著調用算法3GetOutTrv()與算法GetInTrv()計算X(v)的trv旅行時間表（9～10行），最后返回每個節點v的trvout和trvin表，即TD-H2H索引（12行）。TD-H2H索引的大小是以的樹寬與樹高為界的，道路網絡可以分解為低樹高與低樹寬的樹分解[10]，因此，對于現實世界中的大型道路網絡來說，TD-H2H是可行的。

構建時序樹分解的時間復雜度為O(n×w2)，計算位置數組的時間復雜度為O(w×h)。因此，算法4時間復雜度為O(n×(w2+h×w×(α+β)))=O(n×h×w×(α+β)) 。算法4的空間復雜度為O(n×h×I)。

5 時序最短路徑查詢

本章說明如何基于TD-H2H 索引設計高效的進行時序最短路徑查詢的TD-OAI算法。

由上文可知，給定時序圖GT(V,E,F) 的樹分解、TD-H2H 索引以及查詢q(s,d,t)，首先基于性質1獲得s與d之間的點割集X，X為X(s)與X(d)在內的最小公共祖先。接著因為X(s).trvout中已經保存了所有從s到X(s).anc中可達節點的最短旅行時間函數，X(d).trvin中保存了X(d).anc中可以到達d的節點到d的最短旅行時間函數，根據性質2 可得X?X(s).anc且X?X(d).anc，即假設x為X中的節點，如果存在這樣的x:X(s).trvout中保存了從s到x的最短旅行時間函數，且X(d).trvin中保存了從x到d的最短旅行時間函數。說明GT中有從s到d的路徑，使用X(s).trvout[x]和X(d).trvin[x]可以計算出從s出發經過節點x到達d需要的最短時間Trvs,d(t)。如果X中存在不只一個滿足上述條件的x，則需要分別計算對應的Trvs,d(t)，其中最小的Trvs,d(t)即為從s到d在時間t出發需要的最短旅行時間，所對應的路徑為最短路徑。具體過程如算法5所示。

算法5TD-OAI

輸入：、TD-H2H、q(s,d,t)。

輸出：。

給定查詢q(s,d,t)，算法5 首先確定X(s)與X(d)在內的最小公共祖先X（1 行），將最小旅行時間minTrv的初值賦值為最大值。然后根據X內的元素訪問X(s)的out旅行時間函數表X(s).trvout與X(d)的in旅行時間函數表X(d).trvin來回答查詢q（3～10行），迭代次數等于X中元素數量。迭代前判斷X[i]是否是s與d間的中轉節點（5 行），是則計算新的旅行時間（6～7行），若新的旅行時間小于已獲得的最短旅行時間（8行），則進行最短旅行時間的更新（9行），最后返回minTrv（11 行）。注意，算法5 只給出了最小公共祖先X既不是X(s)也不是X(d)的情況，當最小公共祖先為X(s)或X(d)時，s與d間的最短旅行時間函數已經保存為X(s).trvout[d]或X(d).trvin[s]，不再需要中轉節點，直接調用函數就可以計算出s與d之間的最短旅行時間。

算法5 的時間復雜度為O(w×lbS)，其中S為時間函數的平均段數，O(lbS)為使用二分法在段數為S的時間函數內查找指定出發時間t所在函數段的時間復雜度。

例6如圖3 所示，給定時序圖GT、時序樹分解、TD-H2H索引以及查詢q(1,5,0)，首先確定X(1)與X(5)在內的最小公共祖先X(4)={8,7,6,4}，根據X(4)中的元素訪問X(1)的out旅行時間表與X(5)的in旅行時間表。如表3所示，X(4)中沒有元素共同存在于X(1).trvout與X(5).trvin中，因此從節點1 不能到達節點5。給定查詢q(9,5,8)，X(9)與X(5)在內的最小公共祖先X(4)={8,7,6,4}，X(4)中元素8、7 和4 共同存在于X(9).trvout與X(5).trvin中，分別計算trv=X(9).trvout[8](8)+X(5).trvin[8](8+X(9).trvout[8](8))，trv=X(9).trvout[7](8)+X(5).trvin[8](8+X(9).trvout[7](8))，trv=X(9).trvout[4](8)+X(5).trvin[8](8+X(9).trvout[4](8))。其中值最小的trv就是查詢q(9,5,10)的結果，即出發時間為8時，從節點9出發到達節點5所需要的最短時間。

6 實驗

6.1 實驗設置

實驗環境：所有算法都使用C++實現；操作系統是Linux；CPU為Intel 2.20 GHz；內存128 GB。

比較算法：TD-Dijkstra[21]是基于Dijkstra[14]擴展而來的非索引算法，可以用于時序道路網絡上的最短路徑查詢；TD-G-tree[24]是最新的用于最短路徑查詢的時序索引。為說明構建索引的必要性以及本文算法的有效性，將TD-H2H索引與TD-G-tree相比較，與TD-Dijkstra 以及基于TD-G-tree 構建的查詢算法TDSP[24]比較TD-OAI的查詢效率。

實驗數據：如表4 所示，本文使用4 個真實世界的道路網絡數據集進行實驗。本文基于原始數據集上的靜態權重生成時間函數，獲得時序圖。實驗時采用86 400 s的時間閾值，隨機從數據集中選取1 000對源節點與目的節點，并為其分配10 個不同的時間點作為出發時間以生成查詢文件。每次實驗都會進行10 000次最短路徑查詢，統計平均查詢時間。

表4 數據集Table 4 Datasets

6.2 查詢效率評估

本節從三方面評估TD-OAI的查詢效率，查詢結果與TD-Dijkstra以及TDSP進行比較。

（1）有效性測試：首先測試TD-OAI的有效性，有效性測試是指直接在由真實數據集建模得到的4 個時序圖上運行3 個查詢算法，進行時序最短路徑查詢，用以判斷查詢算法是否在不同類型的道路網絡中都能高效地進行最短路徑查詢工作。3 個查詢算法使用同樣的查詢文件，即相同的源節點、目的節點與出發時間。查詢文件中共10 000條查詢，10 000次查詢后，將平均時間作為查詢結果。

如圖5所示，隨著數據集規模的增長，3種查詢算法的查詢時間均呈現出遞增的趨勢。4 個數據集上的運行結果都表明，本文算法TD-OAI效率優于現有算法，非索引算法TD-Dijkstra 明顯比其他兩個基于索引的查詢算法需要更長的平均查詢時間。這是由于TD-Dijkstra 在查詢過程中需要進行多次迭代運算，每次迭代從候選集中選擇與源節點距離最短的節點作為訪問節點，直至找到目的節點。TD-Dijkstra不知道目的節點的位置，只能向所有可能的方向擴展節點，直到發現目的節點為止，當兩個節點距離很遠時TD-Dijkstra可能遍歷整個網絡。TD-G-tree使用分層圖分區將道路網絡劃分為分層分區，產生平衡樹TD-G-tree，索引邊在分區過程中被切割的節點（邊界節點）間的最短旅行時間函數，查詢最短路徑時，利用TD-G-tree 與邊界節點的特性，可以減少查詢時的訪問節點的數量。本文基于點割集與樹分解的概念提出的索引TD-H2H，提前存儲好源節點與目的節點到點割集中節點的最短旅行時間函數，查詢時直接訪問即可，訪問次數以樹分解的寬度w為界，而道路網絡的樹寬通常較小，因此，TD-OAI的查詢速度更快。

圖5 有效性測試Fig.5 Effectiveness experiment

（2）節點數量對查詢效率的影響：為了測試出節點數量對查詢效率的影響，本文在4 個時序圖OL、CAL、NA 與BAY 中分別按照0.2、0.4、0.6 與0.8 的節點數占比提取出4個時序子圖，保證4個子圖內的節點數遞增且相對平均增長，在新得到的16 個子圖中分別運行3個查詢算法。查詢結果如圖6～圖9所示，隨著節點數的增多，3種算法的查詢時間均呈現上升趨勢，TD-Dijkstra持續上升，TD-OAI與TDSP在開始時上升，之后趨于平緩，說明節點數量對基于索引的算法的影響遠小于非索引算法的影響，且TD-OAI的查詢時間遠小于其他兩個算法。隨著圖中節點數量的增多，進行最短路徑查詢時需要訪問的節點數也會增多，因此3個算法的查詢時間均有所增長。基于索引的查詢算法由于索引已經提前保存了部分關鍵最短路徑，查詢時可直接使用，大大減少了需要訪問的節點數量，因而節點數增長對于索引方法的影響要小于非索引方法，進一步說明了索引的必要性。

圖6 節點數測試（OL）Fig.6 Experiment of number of vertices(OL)

圖7 節點數測試（CAL）Fig.7 Experiment of number of vertices(CAL)

圖8 節點數測試（NA）Fig.8 Experiment of number of vertices(NA)

圖9 節點數測試（BAY）Fig.9 Experiment of number of vertices(BAY)

（3）節點的旅行時間長度對查詢效率的影響：評估源節點與目的節點間的旅行時間長度對查詢效率的影響時，本文以源節點與目的節點之間的旅行時間為標準為4 個時序圖分別生成了5 個查詢文件。每個查詢文件中包含104個查詢，每個查詢由源節點、目的節點以及出發時間組成，且為保證旅行時間的遞增和相對平均增長，5個文件中源節點與目的節點間的旅行時間都在特定的范圍內，分別為[0,1.0×104)、[1.0×104,1.0×105)、[3.0×105,5.0×105)、[8.0×105,1.0×106)以及[1.3×106,1.5×106)，單位為s，用以測試在同一個時序道路網絡中，節點間的旅行時間長度對查詢效率的影響。使用3 個查詢算法依次在4 個時序圖上對5個查詢文件進行查詢，其查詢結果如圖10～圖13所示，3種算法的查詢時間整體呈上升趨勢，TD-OAI波動的幅度最小，且查詢時間遠小于其他兩個算法。隨著節點間旅行時間的增大，TD-Dijkstra 需要遍歷的節點數也會變多，進而增大了查詢時間。而基于索引的查詢算法，在索引的作用下，節點間的旅行時間對查詢時間的影響較小，因此，TD-Dijkstra上升趨勢明顯，而另外兩個算法的趨勢較平緩。

圖10 旅行時間測試（OL）Fig.10 Experiment of travelling time(OL)

圖11 旅行時間測試（CAL）Fig.11 Experiment of travelling time(CAL)

圖12 旅行時間測試（NA）Fig.12 Experiment of travelling time(NA)

圖13 旅行時間測試（BAY）Fig.13 Experiment of travelling time(BAY)

6.3 索引評估

本節評估了構建TD-H2H 索引的所需的時間開銷以及空間開銷，分別與TD-G-tree進行比較。圖14說明了索引構建時間，圖15 說明了索引大小。TDH2H 索引包括時序樹分解結構、樹中每個包的位置數組以及旅行時間函數表。索引構建時間包括構建時序樹分解的時間以及計算位置數組和旅行時間函數表的時間。如圖14 所示，TD-H2H 的構建時間與TD-G-tree 的構建時間接近，索引大小比TD-G-tree大，因為相比邊界節點，圖中點割集中的節點更多，根據點割集構造索引，會有更大的空間開銷。

圖14 構建時間Fig.14 Building time

圖15 索引大小Fig.15 Index size

7 結論

本文研究了時序道路網路上的最短路徑查詢問題，基于樹分解的概念提出了TD-H2H索引。為了將樹分解應用于時序圖，提出時序樹分解算法，該方法生成的樹分解可以加速索引的構建。在樹分解結構的基礎上提出了索引TD-H2H 的構建算法。最后基于TD-H2H 索引設計了最短路徑查詢方法TD-OAI。實驗結果表明了本文方法可以有效地解決時序圖上的最短路徑查詢問題。