1. 項目概述

項目說明

該項目分別在DE1-SOC開發(fā)板的FPGA和HPS上實現(xiàn)了Dijkstra算法，能在中國鐵路網(wǎng)中找到兩站之間的最短距離和路線。

這個項目包含304個中國主要火車站。運行程序時，首先在VGA上顯示包含所有火車站及站點之間連線的完整地圖：

然后用戶可以通過輸入兩個站點的名稱，或在VGA屏幕相應的站點上點擊鼠標以選擇任意兩個站點作為起點和目的地，程序會根據(jù)Dijkstra算法很快返回它們之間的最小距離、沿路站點以及計算所耗費時長，并在VGA顯示器上顯示出詳細的路線。

最后他們將兩套方案進行了對比，結果顯示Dijkstra算法在FPGA上實現(xiàn)比僅在HPS上實現(xiàn)的計算速度快10倍。所以利用FPGA并行數(shù)據(jù)處理的優(yōu)勢來加速Dijkstra算法是個非常不錯的選擇。

2. Dijkstra算法

Dijkstra算法用于計算點網(wǎng)絡中兩點之間的最小距離和路徑。由計算機科學家Edsger W. Dijkstra于1956年提出。下圖是這個算法的一個概念解釋:

圓圈內(nèi)的數(shù)字代表火車站，連接兩個圓的線代表鐵路，線旁邊的數(shù)字是鐵路的距離。例如，從1號站到4號站有多種選擇，Dijkstra算法將幫助我們找到1號站到4號站的最短距離。

表1紅框中的第1行表示節(jié)點1與其他每個節(jié)點之間的最小距離。

表1

把1當作起點。為了獲得 1 與其余每個站點之間的最小距離，需多次更新表1紅框中的第 1 行。

首先，從點 1 到點 1 本身，距離為0，這肯定是最短，因此不會再更新這個值，這里把0設定為固定值。

然后找到表1紅框第 1 行中與1連接的最小距離對應的點，即距離為7的點 2 。此時不會再更新 7這個值，因為可以確保它是從點 1 到點 2 的最短距離。這里把7設定為固定值。

接下來，點2 將被視為下一個起點。如果第 1 行 x 列的距離大于第 1 行第 2 列和第 2 行 x 列的距離之和，則將第 1 行 x 列更新為距離之和。x 可以來自{3,4,5,6}中的任意數(shù)字。這樣第一行就更新如下：

表2

現(xiàn)在，除了固定值0和 7 之外，第 1 行中的最小值是 9，對應于點 3。它是從點 1 到點 3 的最短距離，所以此處9也被設定為固定值。

接下來，第 1 行將從第 3列更新。如果第1行x列的距離大于第1行第3列和第3行x列的距離之和，則將第1行x列更新為距離之和。x 可以來自{4,5,6}中的任意數(shù)字。第 1 行更新為：

表3

用同樣的方法，分別更新第1行的4、5和6列。結果如下所示：

表4

這樣就得到了點1與其他每個節(jié)點之間的最小距離。

審核編輯：劉清