【圖論Graph】Part3：最短路徑演算法 - Dijkstra 介紹與實作

上篇進一步認識基本的圖形架構與三大 Graph 算法，那首先從 shortest path 開始，我們會陸續去理解這些算法，以及可能的應用，如果還沒有看過上一篇的，可以點以下連結～那我們就開始吧！

【圖論Graph】Part1：初探圖形與圖形演算法之應用

【圖論Graph】Part2：深入認識Graph的基本概念、組成和應用

Photo by Justin Kauffman on Unsplash

最短路徑介紹

• 定義：用來算一對節點之間的最短(加權)路徑
• 應用場景：
  1. 查找位置之間的路徑，例如 Google 地圖
  2. 社交網路中人與人之間的分離程度，例如 Linkedin 查找人之間的幾度關聯

Dijkstra 演算法介紹

• 算法說明：從起始節點開始，找到直接關係中的最小權重，追蹤這些權重，移動到最近的節點，直到達成目標。
• 可以參考：【算法】最短路径查找—Dijkstra算法

實作 neo4j 利用 Dijkstra 計算最短路徑

分成以下幾個步驟：

1. 安裝 gds 相關套件：舊版本的 neo4j 是使用 algo 的套件，而此寫法在新版(Version 1.5.7) 的 neo4j 已不支援。

2. 創造資料

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);

3. 映射到 graph

CALL gds.graph.project(
    'myGraph',
    'Location',
    'ROAD',
    {
        relationshipProperties: 'cost'
    }
)

4. 利用算法 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

5. 結果

獲得 A → 各點的路徑距離，分別是 0, 50, 90, 120, 160

參考資料

• Dijkstra Source-Target Shortest Path
• Neo4j gds - Graph algorithms

小心得

今天實作第一個最短路徑算法，在圖形資料的世界裡，會想知道兩個點之間到底通過多少個邊相連才能夠抵達，而這時候最短路徑就可以派上用場，尤其當資料量越大、節點與邊數量越多越複雜時，依照問題與應用場景選對算法就變得很重要。

舉例來說：對於 Google 地圖在查找兩點之間的路徑時，篩選出 user 適合的一條道路其實不容易，背後需要考量不同的原則例如最少時間、最短距離，要解決這一題時，就需要選適合的算法，這也是不同的算法存在與改良的意義，才能在有限的資源與時間下計算出來～這個過程蠻有趣的。

下一篇預計會寫認識其他的最短路徑，有興趣的可以追蹤一下，下次見囉！