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

更新於 發佈於 閱讀時間約 5 分鐘

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

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

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

Photo by Justin Kauffman on Unsplash

Photo by Justin Kauffman on Unsplash


最短路徑介紹

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

Dijkstra 演算法介紹

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

分成以下幾個步驟:

  1. 安裝 gds 相關套件:舊版本的 neo4j 是使用 algo 的套件,而此寫法在新版(Version 1.5.7) 的 neo4j 已不支援。
raw-image
  1. 創造資料
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);
  1. 映射到 graph
CALL gds.graph.project(
'myGraph',
'Location',
'ROAD',
{
relationshipProperties: 'cost'
}
)
  1. 利用算法 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
  1. 結果
raw-image

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

參考資料

小心得

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

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

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

avatar-img
33會員
44內容數
歡迎來到《桃花源記》專欄。這裡不僅是一個文字的集合,更是一個探索、夢想和自我發現的空間。在這個專欄中,我們將一同走進那些隱藏在日常生活中的"桃花源"——那些讓我們心動、讓我們反思、讓我們找到內心平靜的時刻和地方
留言
avatar-img
留言分享你的想法!

































































Karen的沙龍 的其他內容
本篇文章深入介紹了圖形的基本概念、組成和應用。從圖形的基本組成,到圖的類型與種類,再到圖形演算法的三大類型,本文將接續圖形領域的深入學習,並分享了對圖形的初步認識和學習方向的小心得。希望對正在學習圖形的人有所幫助。
0/5Graph
圖形演算法在資料處理上扮演重要角色。本文介紹圖形的歷史、定義、技術用途,以及為什麼我們要關心圖形演算法。文末還提及圖形演算法在機器學習領域的應用。下次將介紹更詳細的圖形演算法內容。
參加Leetcode的30 Days of Pandas挑戰,除了是學習的機會,更是練習熟悉pandas功能的機會。文章分享了挑戰簡介、題目描述、關鍵技術以及參加挑戰的心得。適合新手學習pandas,也可提升熟練度。
這篇文章將分享最近遇到 NVIDIA GPU driver 的問題,並提供瞭解決步驟,以及證實問題解決的測試方法。當您遇到類似問題時,可以參考這篇文章進行解決。文章中包含了定位庫文件目錄、備份和替換文件以及測試修改的步驟。
前言 前幾篇分享了 IBM Watsonx.ai 平台,以及在平台上使用 LLM 完成客戶體驗分析、與LLM串連處理較複雜的問題。在這一篇中,我們想來嘗試使用檢索增強生成(RAG)的技術,RAG 通過整合外部數據來增強基礎模型的回答能力,這不僅能解決模型訓練數據的局限性問題,還可以提供更精準和相關
前言 在先前的文章中,我們探討了 IBM Watsonx 在客戶滿意度分析中的應用。今天,我們將利用 Google 的兩款大型語言模型(LLM)— flan-ul2 和 flan-t5-xxl,展示它們如何串聯起來生成關於特定主題的隨機問題和回答。 在這篇文章中,將使用 SimpleSequen
本篇文章深入介紹了圖形的基本概念、組成和應用。從圖形的基本組成,到圖的類型與種類,再到圖形演算法的三大類型,本文將接續圖形領域的深入學習,並分享了對圖形的初步認識和學習方向的小心得。希望對正在學習圖形的人有所幫助。
0/5Graph
圖形演算法在資料處理上扮演重要角色。本文介紹圖形的歷史、定義、技術用途,以及為什麼我們要關心圖形演算法。文末還提及圖形演算法在機器學習領域的應用。下次將介紹更詳細的圖形演算法內容。
參加Leetcode的30 Days of Pandas挑戰,除了是學習的機會,更是練習熟悉pandas功能的機會。文章分享了挑戰簡介、題目描述、關鍵技術以及參加挑戰的心得。適合新手學習pandas,也可提升熟練度。
這篇文章將分享最近遇到 NVIDIA GPU driver 的問題,並提供瞭解決步驟,以及證實問題解決的測試方法。當您遇到類似問題時,可以參考這篇文章進行解決。文章中包含了定位庫文件目錄、備份和替換文件以及測試修改的步驟。
前言 前幾篇分享了 IBM Watsonx.ai 平台,以及在平台上使用 LLM 完成客戶體驗分析、與LLM串連處理較複雜的問題。在這一篇中,我們想來嘗試使用檢索增強生成(RAG)的技術,RAG 通過整合外部數據來增強基礎模型的回答能力,這不僅能解決模型訓練數據的局限性問題,還可以提供更精準和相關
前言 在先前的文章中,我們探討了 IBM Watsonx 在客戶滿意度分析中的應用。今天,我們將利用 Google 的兩款大型語言模型(LLM)— flan-ul2 和 flan-t5-xxl,展示它們如何串聯起來生成關於特定主題的隨機問題和回答。 在這篇文章中,將使用 SimpleSequen
你可能也想看
Google News 追蹤
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。
Thumbnail
題目敘述: Minimum Cost to Convert String I 給定字元轉換映射表original, changes和對硬的成本陣列cost。 請問字串source轉換到字串destination的最小成本是多少? 如果無解,請返回-1 如果有解,請返回整體的轉換最小成本。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
重點先說,我將累積近九年學習圖解的知識與經驗,彙整成30個單元的「圖解力全攻略」線上課程,超狂優惠只到6/30! 立即加入「圖解力全攻略」:https://drawwin.kaik.io/courses/drawtowin 輸入drawtowin折扣碼,再折500元
Thumbnail
題目敘述 All Ancestors of a Node in a Directed Acyclic Graph 給定一個有向無環圖,請找出每個點的祖先,以陣列的形式返回答案。
Thumbnail
Minimum Path Sum 給定一個矩陣,每個格子點代表經過的對應成本。 每回合可以往右移動一格或往下移動一格。 請問從起點左上角 走到 終點右下角的最小路徑成本總和是多少?
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。
Thumbnail
題目敘述: Minimum Cost to Convert String I 給定字元轉換映射表original, changes和對硬的成本陣列cost。 請問字串source轉換到字串destination的最小成本是多少? 如果無解,請返回-1 如果有解,請返回整體的轉換最小成本。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
重點先說,我將累積近九年學習圖解的知識與經驗,彙整成30個單元的「圖解力全攻略」線上課程,超狂優惠只到6/30! 立即加入「圖解力全攻略」:https://drawwin.kaik.io/courses/drawtowin 輸入drawtowin折扣碼,再折500元
Thumbnail
題目敘述 All Ancestors of a Node in a Directed Acyclic Graph 給定一個有向無環圖,請找出每個點的祖先,以陣列的形式返回答案。
Thumbnail
Minimum Path Sum 給定一個矩陣,每個格子點代表經過的對應成本。 每回合可以往右移動一格或往下移動一格。 請問從起點左上角 走到 終點右下角的最小路徑成本總和是多少?