1. 項(xiàng)目概述

項(xiàng)目說明

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

這個(gè)項(xiàng)目包含304個(gè)中國主要火車站。運(yùn)行程序時(shí)，首先在VGA上顯示包含所有火車站及站點(diǎn)之間連線的完整地圖：

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

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

2. Dijkstra算法

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

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

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

表1

把1當(dāng)作起點(diǎn)。為了獲得 1 與其余每個(gè)站點(diǎn)之間的最小距離，需多次更新表1紅框中的第 1 行。

首先，從點(diǎn) 1 到點(diǎn) 1 本身，距離為0，這肯定是最短，因此不會(huì)再更新這個(gè)值，這里把0設(shè)定為固定值。

然后找到表1紅框第 1 行中與1連接的最小距離對應(yīng)的點(diǎn)，即距離為7的點(diǎn) 2 。此時(shí)不會(huì)再更新 7這個(gè)值，因?yàn)榭梢源_保它是從點(diǎn) 1 到點(diǎn) 2 的最短距離。這里把7設(shè)定為固定值。

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

表2

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

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

表3

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

表4

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

審核編輯：劉清