首先，引進(jìn)一個(gè)輔助向量D，它的每個(gè)分量D[i]表示當(dāng)前所找到的從始點(diǎn)v0到每個(gè)終點(diǎn)vi的最短路徑的長(zhǎng)度。

它的初態(tài)為：若從v0到vi有弧，則D[i]為弧上的權(quán)值；否則，置D[i]為∞。

顯然，長(zhǎng)度為
D[j]=Min{D[i]|vi∈V-S}, S初值為{v0}
的路徑就是從v0出發(fā)的長(zhǎng)度最短的一條路徑。
此路徑為（v0, vj）。

那么，下一條長(zhǎng)度次短的路徑是哪一條呢？
假設(shè)該次短路徑的終點(diǎn)是vk，可想而知，這條路徑或者是（v0, vk），或者是（v0, vj, vk）。

它的長(zhǎng)度或者是從v0到vk的弧上的權(quán)值，或者是D[j]和從vj到vk的弧上的權(quán)值之和。

在一般情況下，下一條長(zhǎng)度次短的路徑的長(zhǎng)度必是
D[j]=Min{D[i]|vi∈V-S}
其中，D[i]或者是弧（v0, vi）上的權(quán)值，或者是D[k]（vk∈S和弧（vk, vi）上的權(quán)值之和。

根據(jù)以上分析，可以得到如下描述的算法。

假設(shè)用帶權(quán)的鄰接矩陣arcs表示帶權(quán)有向圖，arcs[i][j]表示弧〈vi, vj〉上的權(quán)值。

若〈vi, vj〉不存在，則置arcs[i][j]為∞（在計(jì)算機(jī)上可用允許的最大值代替）。

S為已找到從v0出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)S={v0}。

那么，從v0出發(fā)到圖上其余各頂點(diǎn)vi可能達(dá)到最短路徑長(zhǎng)度的初值為 D[i]=arcs[LocateVertex(G,v0)][i],
vi∈V-S

選擇vj，使得 D[j]=Min{D[i]|vi∈V-S} vj就是當(dāng)前求得的一條從v0出發(fā)的最短路徑的終點(diǎn)。令S=S∪{vj}。

（3）修改從v0出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度。如果 D[j]+arcs[j][k]<D[k] 則修改D[k]為
D[k]=D[j]+arcs[j][k] 重復(fù)操作步驟（2）和步驟（3）共n-1次。

由此求得從v0到圖上其余各頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。

用C++語(yǔ)言描述的Dijkstra算法如下:

#include <iostream> using namespace std;const int MAXW = 30000; const int MaxVertexNum = 30; typedef int VertexType; class MGraph { public:void CreateGraph();void ShortestPath_Dij(int v0);void Print_Path_Dij(int v0);private:int vertexnum;VertexType vertexs[MaxVertexNum];int edgenum;int P[MaxVertexNum];int D[MaxVertexNum];int arcs[MaxVertexNum][MaxVertexNum]; };void MGraph::CreateGraph() {cout << "請(qǐng)輸入節(jié)點(diǎn)數(shù)和邊條數(shù)" << endl;cin >> vertexnum >> edgenum;for (int i = 0; i < vertexnum; i++)for (int j = 0; j < vertexnum; j++)arcs[i][j] = MAXW;cout << "請(qǐng)依次輸入按序號(hào)0到n頂點(diǎn)的中存儲(chǔ)的信息" << endl;for (int i = 0; i < vertexnum; i++){cin >> vertexs[i];}cout << "下面輸入邊的信息" << endl;for (int i = 0; i < edgenum; i++){int v1, v2, w;cout << "輸入邊<i,j>對(duì)應(yīng)的頂點(diǎn)序號(hào)i,j,然后再輸入該邊的權(quán)值" << endl;cin >> v1 >> v2 >> w;arcs[v1][v2] = w;} }void MGraph::ShortestPath_Dij(int v0) {bool f[MaxVertexNum];for (int v = 0; v <vertexnum; v++){f[v] = false;D[v] = arcs[v0][v];P[v] = -1;if (D[v] < MAXW) P[v] = v0;}D[v0] = 0;f[v0] = true;for (int i = 0; i < vertexnum; i++){int v = -1;int min = MAXW;for (int w = 0; w < vertexnum; w++)if (!f[w] && D[w] < min){v = w;min = D[w];}if (v == -1) break;f[v] = true;for (int w = 0; w < vertexnum; w++){if (!f[w] && (min + arcs[v][w] < D[w])){D[w] = min+arcs[v][w];P[w] = v;}}} }void MGraph::Print_Path_Dij(int v0) {cout << "The shortest path from Vertex:" << v0 << " to the other Vertex:" << endl;for (int v = 0; v < vertexnum; v++){if (P[v] == -1)continue;cout << D[v] << " ";cout << v << "<=";int i = v;while (P[i] != -1){cout << P[i] << "<=";i = P[i];}cout << endl;} }int main() {MGraph g;g.CreateGraph();int v0;cin >> v0;g.ShortestPath_Dij(v0);g.Print_Path_Dij(v0);return 0; }

測(cè)試結(jié)果:

以上代碼存在一點(diǎn)小問(wèn)題，有時(shí)間我會(huì)進(jìn)行修改的，我最新發(fā)布的dijkstra的代碼是正確的，可以在我的博客主頁(yè)搜索找一下。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的C++ 实现带权有向图的单源点最短路径Dijkstra算法(完整代码)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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