AnzoGraph由Netezza背後的工程師和Amazon Redshift背後的技術構建，是一種原生的大規模並行處理（MPP）分布式圖形OLAP（GOLAP）資料庫，其執行查詢的速度比其他供應商快100倍。圖算法提供了建模和預測複雜動態的手段，例如資源或信息流，傳染或網絡故障傳播的途徑，以及群體的影響和彈性。
本文旨在幫助您更好地利用圖形分析和圖形算法，以便您可以使用圖形資料庫更快地有效地創新和開發智能解決方案。上一次，我們使用Neo4j中的示例，重點介紹了尋路和圖搜索算法，重點是單源最短路徑算法。這一次，我們將研究另一個算法，查看All Pairs Shortest Path算法，該算法用於評估高速公路備份或網絡容量等情況下的備用路由。它也是提供多路徑的邏輯路由的關鍵，例如在發生故障時的呼叫路由選擇。
關於所有最短路徑
All Pairs Shortest Path（APSP）算法計算所有節點對之間的最短（加權）路徑。該算法具有優化，使其比為圖中的每對節點調用單源最短路徑算法更快。某些節點對可能無法彼此訪問，因此這些對之間不存在最短路徑。在這種情況下，算法返回這些節點對之間的無窮大值。
什麼時候應該使用所有最短路徑？
All Pairs Shortest Path算法用於城市服務系統問題，例如城市設施的位置或貨物的分配或交付。這方面的一個例子是確定在運輸網格的不同段上預期的交通負荷。有關更多信息，請參閱城市運營研究。
所有Pairs Shortest Path都用作REWIRE數據中心設計算法的一部分，該算法可以找到具有最大帶寬和最小延遲的網絡。
所有最短路徑示例
讓我們計算一個小數據集上的All Pairs Shortest Path。
以下Cypher語句創建一個包含它們之間位置和連接的示例圖。
MERGE （a：Loc { name：「A」 } ）
MERGE （b：Loc { name：「B」 } ）
MERGE （c：Loc { name：「C」 } ）
MERGE （d：Loc { name：「D」 } ）
MERGE （e：Loc { name：「E」 } ）
MERGE （f：Loc { name：「F」 } ）
合併 （a ） - [ ：ROAD { cost：50 } ] - > （b ）
合併 （a ） - [ ：ROAD { cost：50 } ] - > （c ）
合併 （a ） - [ ：ROAD { cost：100 } ] - > （d ）
MERGE （b ） - [ ：ROAD { cost：40 } ] - > （d ）
合併 （c ） - [ ：ROAD { cost：40 } ] - > （d ）
MERGE （c ） - [ ：ROAD { cost：80 } ] - > （e ）
MERGE （d ） - [ ：ROAD { cost：30 } ] - > （e ）
MERGE （d ） - [ ：ROAD { cost：80 } ] - > （f ）
MERGE （e ） - [ ：ROAD { cost：40 } ] - > （f ）;
結論
在過去的幾周裡，我們通過查看尋路和圖搜索算法來了解一些用例，包括本周的All Pairs Shortest Path。下一次，我們將繼續檢查這些類型的算法，概述最小權重生成樹算法，該算法計算具有最小值的連接結構的路徑（關係的權重，如成本時間或容量）與訪問所有節點相關聯。