上篇進一步認識基本的圖形架構與三大 Graph 算法，那首先從 shortest path 開始，我們會陸續去理解這些算法，以及可能的應用，如果還沒有看過上一篇的，可以點以下連結～那我們就開始吧！
【圖論Graph】Part2：深入認識Graph的基本概念、組成和應用
Photo by Justin Kauffman on Unsplash
最短路徑介紹
- 定義：用來算一對節點之間的最短(加權)路徑
- 應用場景：
1. 查找位置之間的路徑，例如 Google 地圖
2. 社交網路中人與人之間的分離程度，例如 Linkedin 查找人之間的幾度關聯
Dijkstra 演算法介紹
- 算法說明：從起始節點開始，找到直接關係中的最小權重，追蹤這些權重，移動到最近的節點，直到達成目標。
- 可以參考：【算法】最短路径查找—Dijkstra算法
實作 neo4j 利用 Dijkstra 計算最短路徑
分成以下幾個步驟：
- 安裝 gds 相關套件：舊版本的 neo4j 是使用 algo 的套件，而此寫法在新版(Version 1.5.7) 的 neo4j 已不支援。
- 創造資料
CREATE (a:Location {name: 'A'}),
(b:Location {name: 'B'}),
(c:Location {name: 'C'}),
(d:Location {name: 'D'}),
(e:Location {name: 'E'}),
(f:Location {name: 'F'}),
(a)-[:ROAD {cost: 50}]->(b),
(a)-[:ROAD {cost: 50}]->(c),
(a)-[:ROAD {cost: 100}]->(d),
(b)-[:ROAD {cost: 40}]->(d),
(c)-[:ROAD {cost: 40}]->(d),
(c)-[:ROAD {cost: 80}]->(e),
(d)-[:ROAD {cost: 30}]->(e),
(d)-[:ROAD {cost: 80}]->(f),
(e)-[:ROAD {cost: 40}]->(f);
- 映射到 graph
CALL gds.graph.project(
'myGraph',
'Location',
'ROAD',
{
relationshipProperties: 'cost'
}
)
- 利用算法 Dijkstra 計算最短路徑
MATCH (source:Location {name: 'A'}), (target:Location {name: 'F'})
CALL gds.shortestPath.dijkstra.stream('myGraph', {
sourceNode: source,
targetNode: target,
relationshipWeightProperty: 'cost'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
index,
gds.util.asNode(sourceNode).name AS sourceNodeName,
gds.util.asNode(targetNode).name AS targetNodeName,
totalCost,
[nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
costs,
nodes(path) as path
ORDER BY index
- 結果
獲得 A → 各點的路徑距離，分別是 0, 50, 90, 120, 160
參考資料
小心得
今天實作第一個最短路徑算法，在圖形資料的世界裡，會想知道兩個點之間到底通過多少個邊相連才能夠抵達，而這時候最短路徑就可以派上用場，尤其當資料量越大、節點與邊數量越多越複雜時，依照問題與應用場景選對算法就變得很重要。
舉例來說：對於 Google 地圖在查找兩點之間的路徑時，篩選出 user 適合的一條道路其實不容易，背後需要考量不同的原則例如最少時間、最短距離，要解決這一題時，就需要選適合的算法，這也是不同的算法存在與改良的意義，才能在有限的資源與時間下計算出來～這個過程蠻有趣的。
下一篇預計會寫認識其他的最短路徑，有興趣的可以追蹤一下，下次見囉！
