最短路徑之Dijkstra算法
（一）Dijkstra算法

單源最短路徑：就是從某一個(gè)頂點(diǎn)出發(fā)，到圖中任意頂點(diǎn)之間的最短路徑；

【算法概述】：Dijkstra算法適用于解決單源最短路徑的問(wèn)題。即：從源點(diǎn)到任意指定頂點(diǎn)之間的最短距離的問(wèn)題；但Dijkstra算法要求所有邊的權(quán)值非負(fù)。看過(guò)Prime算法的同學(xué)都知道，Dijkstra算法與Prime算法很相似，不同的就是dis數(shù)組的更新方式。Dijkstra算法用鄰接矩陣存圖比較方便。

【算法思想】：先用一個(gè)數(shù)組記錄從源點(diǎn)到圖中個(gè)頂點(diǎn)直接相連的距離，如果不直接連，就記錄為無(wú)窮大，然后通過(guò)對(duì)該數(shù)組的更新，使得dis[x]表示從源點(diǎn)到x的最短路徑；

1.1 初始化

用鄰接矩陣來(lái)存圖，先進(jìn)行初始化，自己到自己的距離初始化為0，到另外的頂點(diǎn)的距離初始化為無(wú)窮大。并將標(biāo)記數(shù)組都置為0，表示所有頂點(diǎn)都未訪問(wèn)；

void init(){for(i

總結(jié)

以上是生活随笔為你收集整理的数据结构——最短路径之Dijkstra算法(与最小生成树的prime算法很像，建议一起看)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。