本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。

最短路徑—dijkstra算法和Floyd算法

注意：以下代碼 只是描述思路，沒有測(cè)試過！！

dijkstra算法

1.定義概覽

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。注意該算法要求圖中不存在負(fù)權(quán)邊。

問題描述：在無向圖 G=(V,E) 中，假設(shè)每條邊 E[i] 的長(zhǎng)度為 w[i]，找到由頂點(diǎn) V0 到其余各點(diǎn)的最短路徑。（單源最短路徑）

2.算法描述

1)算法思想：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。

2)算法步驟：

a.初始時(shí)，S只包含源點(diǎn)，即S＝{v}，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U={其余頂點(diǎn)}，若v與U中頂點(diǎn)u有邊，則

  本文關(guān)鍵詞：dijkstra算法，，由筆耕文化傳播整理發(fā)布。