?Dijkstra的主要特點(diǎn)是以起始點(diǎn)為中心向外層層拓展（廣度優(yōu)先搜索思想），直到拓展到終點(diǎn)為止。

用二維數(shù)組edge表示頂點(diǎn)之間的關(guān)系，dis數(shù)組表示源點(diǎn)到其余各點(diǎn)的距離，book數(shù)組表示dis對應(yīng)的距離是否是最短距離。

dis數(shù)組初始化為【0，2，6，4】，book為【1，0，0，0】

• 既然是求點(diǎn)1到其余各點(diǎn)的距離，那么，就找一個離點(diǎn)1最近的點(diǎn)。通過dis數(shù)組可知，為點(diǎn)2，這個圖所有的邊為正數(shù)，如果通過另一個點(diǎn)周轉(zhuǎn)，必然大于點(diǎn)1到點(diǎn)2的距離。因此，book更新為【1，1，0，0】。然后，更新dis數(shù)組，查看是否有點(diǎn)經(jīng)過點(diǎn)2周轉(zhuǎn)之后，到達(dá)源點(diǎn)1的距離縮短了。發(fā)現(xiàn)dis[3] = 6, dis[2] + edge[2][3] = 5 < 6，dis更新為【0，2，5，4】（這個更新的過程叫“松弛”）
• 重復(fù)上述的過程，第二輪迭代找到的點(diǎn)為點(diǎn)4，更新book為【1，1，0，1】，剩下的點(diǎn)3經(jīng)過點(diǎn)4周轉(zhuǎn)并不能縮小到源點(diǎn)的距離，因此，dis依然為【0，2，5，4】；
• 第三輪迭代，確定點(diǎn)3，book更新為【1，1，1，1】，算法結(jié)束。

可以發(fā)現(xiàn)，每一輪迭代都可以確定一個點(diǎn)到源點(diǎn)的距離，因此，最多進(jìn)行n-1次“松弛”，就可以結(jié)束算法。

算法圖解，參考該博客：https://blog.csdn.net/heroacool/article/details/51014824

代碼

#include <iostream> using namespace std; const int inf = 0x3f3f3f3f; int edge[5][5] = {{-1,-1,-1,-1,-1},{-1, 0, 2, 6, 4},{-1, inf, 0,3, inf},{-1, 7, inf, 0, 1},{-1, 5, inf, 12, 0} };int main() {const int n = 4;//點(diǎn)的數(shù)量int dis[n+1];//當(dāng)前各點(diǎn)到源點(diǎn)的距離int book[n+1];//各點(diǎn)到源點(diǎn)是否為最小值//初始化，設(shè)源點(diǎn)為n1for (int i = 1; i <= n; ++i)dis[i] = edge[1][i];//book數(shù)組初始化memset(book, 0, sizeof(book));book[1] = 1;int min;//當(dāng)前，未確定最短路徑的點(diǎn)，到源點(diǎn)的最小距離大小//Dijkstra算法核心語句for (int i = 1; i <= n - 1; ++i) {//找到離1號頂點(diǎn)最近的頂點(diǎn)min = inf;int u;for (int j = 1; j <= n; ++j) {if (book[j] == 0 && dis[j] < min) {min = dis[j];u = j;}}//每輪迭代都可以確定一個點(diǎn)到源點(diǎn)的最短距離，因此只要迭代n-1輪book[u] = 1;//通過已經(jīng)確定的點(diǎn)，對dis數(shù)組進(jìn)行更新//（未確定的點(diǎn)通過點(diǎn)u，縮小了到源點(diǎn)的距離）for (int v = 1; v <= n; ++v) {if (edge[u][v] < inf) {if (dis[v] > dis[u] + edge[u][v])dis[v] = dis[u] + edge[u][v];}}}//輸出結(jié)果for (int i = 1; i <= n; ++i)cout << dis[i] << ' ';system("pause");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Dijkstra（单源最短路径）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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