求解最短路徑的相關(guān)算法概述針對最短路徑的算法，將其分為靜態(tài)算法和動態(tài)算法。而本文研究的實際交通路網(wǎng)中的結(jié)點與道路信息，屬于靜態(tài)最短路徑問題。所以，可以應(yīng)用的主要算法包括Dijkstra算法、Floyd算法、A*算法等。1.1Dijkstra算法在靜態(tài)最短路徑問題中，由荷蘭科學(xué)家E.W.Dijkstra的Dijkstra算法，是使用最為廣泛的算法之一。Dijkstra算法又稱“迪克斯特拉算法”，主要應(yīng)用于解決單源最短路徑問題。算法基于貪心策略，運行的每一步都是最優(yōu)解。而算法的特征是將起始點作為搜索的中心點，以圓形向外層層擴展搜索，一直向外延伸，直到將終點包含其中。搜索面積為以起始結(jié)點到終點的距離為半徑的同心圓面積。搜索結(jié)果十分精確，保證了路徑質(zhì)量。而在這個過程中，不能出現(xiàn)負權(quán)值，否則會陷入循環(huán)，無法實現(xiàn)目的【8】。算法在運行中，將道路網(wǎng)中的結(jié)點分為三種類型：未標(biāo)記的結(jié)點、臨時標(biāo)記的結(jié)點以及永久標(biāo)記的結(jié)點。而Dijkstra算法的思想是以起始點為根基，遍歷起始點周圍所用的結(jié)點，將其中最短的結(jié)點標(biāo)記為永久標(biāo)記結(jié)點，并以此結(jié)點為下一個根基，重復(fù)以上過程，直到搜索到終點為止。而在遍歷的過程中，其余較短的結(jié)點均存于臨時標(biāo)記的結(jié)點中，未經(jīng)遍歷的結(jié)點存于未標(biāo)記的結(jié)點中。值得一提的是，在Dijkstra算法中，臨時標(biāo)記的結(jié)點在存儲過程中是沒有順序的。所以，Dijkstra算法每運行一次，查找一次最短路徑，都必須將所以的臨時標(biāo)記的結(jié)點進行遍歷，這也是Dijkstra算法存在的問題。總而言之，Dijkstra算法是根據(jù)路徑的權(quán)值的大小有序的生成的最短路徑算法。圖3：Dijkstra算法算法步驟：將所以結(jié)點初始化，將圖中的所以結(jié)點變?yōu)槲礃?biāo)記結(jié)點。同時，將起始結(jié)點置入CLOSE表中，其余結(jié)點置入OPEN表中。取CLOSE表中的最后一個結(jié)點作為當(dāng)前結(jié)點，查找OPEN表中的結(jié)點，判斷兩者之間的距離，有更小的權(quán)值就更新。將具有最小權(quán)值的結(jié)點置入CLOSE表中，同時在OPEN表中刪除該結(jié)點。判斷OPEN結(jié)點是否為空，如果為空，則重復(fù)以上步驟。如果OPEN結(jié)點不為空，運算結(jié)束，輸出最短路徑。算法流程圖：除此之外，算法仍存在幾個不足：在數(shù)據(jù)存儲時，Dijkstra算法是采用鄰接矩陣儲存路網(wǎng)，其儲存大小為n×n。因此，算法在計算最短路徑的過程中進行了多次遍歷，時間復(fù)雜度為O（n2）。雖然路網(wǎng)中的結(jié)點很多，但是與結(jié)點相連的結(jié)點數(shù)量并不多，即路網(wǎng)圖為稀疏圖。所以，鄰接矩陣的存儲方式對路網(wǎng)太過浪費，并計算了許多無意義的數(shù)據(jù)。所以，存儲效率和計算效率極低。在更新最小權(quán)值的過程中，需要比較所有在OPEN表中的結(jié)點數(shù)據(jù)，要進行大量重復(fù)操作，效率極低。以圓形面積搜索，雖然精準(zhǔn)，但搜索面積過大，十分浪費。1.2Floyd算法Floyd算法又稱“弗洛伊德算法”，由斯坦福教授羅伯特弗洛伊德創(chuàng)造【9】。此算法基于動態(tài)規(guī)劃思想，旨在求算出在圖中每一對結(jié)點之間的最短路徑，也可將算法看成多次運算的Dijkstra算法，結(jié)構(gòu)緊湊。值得一提的時，F(xiàn)loyd算法可以應(yīng)用在邊權(quán)值為負的圖中，在稠密圖中的運行效果最佳。算法步驟：初始化圖中所有的結(jié)點，并進行編號V1、V2、…Vn。同時，初始化矩陣D0。若結(jié)點Vi到Vj之間存在帶有權(quán)值的相同的邊，是兩結(jié)點之間的距離。如果兩結(jié)點之間不存在相通的邊，則dij長度無窮大（∞）；對于每一對的頂點，采取遞歸公式：dij=min{dik+dkj，dij}其中k代表圖中的結(jié)點，計算每對頂點之間的距離，當(dāng)存在更短距離時進行更新。算法結(jié)束后，矩陣Dn中的元素即表示結(jié)點之間的最短路徑長度。由以上過程可以看出，該算法在計算的過程中，必須計算n個矩陣，而且每個矩陣含有n×n個元素，所以其時間復(fù)雜度為O（n3）。由于Floyd算法和Dijkstra算法類似，對這兩種算法的基本情況進行歸納和比較：Dijkstra算法Floyd算法適用范圍有向圖和無向圖有向圖和無向圖功能可以用于單源單匯最短路徑問題用于求所有頂點之間的最短路徑時間復(fù)雜度O（n2）O（n3）權(quán)值要求正權(quán)值正權(quán)值和負權(quán)值聯(lián)系Floyd算法可以用重復(fù)的n次Dijkstra算法來代替表1：算法對比1.3A*算法除了前兩種算法之外，由Hart等人提出的搜索算法——A*算法，也是一種比較智能和經(jīng)典的算法。如果將Dijkstra算法看為基礎(chǔ)，那么A*算法就是在此基礎(chǔ)上生成的創(chuàng)新之花。A*算法的閃亮之處在于在原有的基礎(chǔ)上加入了啟發(fā)式機制，引入一個估價函數(shù)。這不僅是將未搜索點與起始結(jié)點之間的關(guān)系考慮進去，也將未搜索點與終點之間的關(guān)系也考慮在內(nèi)，以此來保證搜素方向是不斷向終點方向進行的，大大的提高了搜索的效率。A*算法的啟發(fā)函數(shù)如下：F（n）=G（n）+H（n）（2.1）式中：F（n）代表結(jié)點n的代價；G（n）表示從起始結(jié)點到結(jié)點n的實際花費代價；H（n）是從結(jié)點到終點的預(yù)估代價。所以，A*算法將實際花費代價與終止結(jié)點代價估值一同考慮在內(nèi)，改進了Dijkstra算法的盲目性，有效減少搜索節(jié)點數(shù)，提高效率。具體算法流程圖：從上可以看出，對OPEN表中和CLOSE表中結(jié)點的存取都要進行耗時的搜索【10】。（算法的不足9）當(dāng)然，A*算法依舊存在一些不足，針對此，進行分析：A*算法的優(yōu)點在于引入了估價函數(shù)，但也是因為這樣，由經(jīng)驗確定的啟發(fā)式函數(shù)，導(dǎo)致了結(jié)點的選擇充滿未知性，無法保證選擇呈現(xiàn)最優(yōu)。很有可能會出現(xiàn)選擇錯誤最優(yōu)結(jié)點，導(dǎo)致其被刪除，這