最短路徑（DP的應用）
單源最短路徑，不允許出現負環
核心思想：更新估算距離，松弛
$$\delta (u,v)\le \delta (u,x)+\delta (x,v)$$

時間復雜度與采用的數據結構有關，標準的dijkstra應該是用堆實現的。
Array O($v^2$)
Binary heap O($(V+E)lgV$)
Fibonacci heap O($E+VlgV$)

如果對于所有的邊權值均為1，那么Dijkstra算法可以用BFS實現
使用FIFO隊列代替Priority隊列，其時間復雜度為O($V+E$)

數組實現：

#include <iostream> using namespace std; void dijkstra(); int e[10][10]; int vis[10]; int dis[10]; int n, m; int min1 = 99999999; int u = 0; int main() {cin >> n >> m;// 初始化鄰接表for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (i == j){e[i][j] = 0;}else{e[i][j] = 99999999;}}}// 填充數據for (int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;e[a][b] = c;}for (int i = 1; i <= n; i++){dis[i] = e[1][i];}vis[1] = 1;dijkstra();for (int i = 1; i <= n; i++){cout << dis[i];}system("pause");return 0; } void dijkstra() {for (int i = 1; i <= n - 1; i++){min1 = 99999999;// 尋找權值最小的點ufor (int j = 1; j <= n; j++){if (vis[j] == 0 && dis[j] < min1){min1 = dis[j];u = j;}}vis[u] = 1;for (int v = 1; v <= n; v++){// 對于每個u可達的v來說if (e[u][v] < 99999999){// 如果當前的dis[v]不滿足三角形不等式，那么進行松弛操作if (dis[v] > dis[u] + e[u][v]){dis[v] = dis[u] + e[u][v];}}}} }

堆實現

#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; const int Ni = 10000; const int INF = 1 << 27; struct node {int point, value;// 構造node(int a, int b){point = a;value = b;}// 重載<操作符bool operator<(const node &a) const{// 對小于運算符進行重載，如果兩個值相等，那么繼續判斷point，如果不等，則返回falseif (value == a.value){return point < a.point;}else{return value > a.value;}} }; vector<node> e[Ni]; int dis[Ni], n; priority_queue<node> q; void dijkstra(); int main() {int a, b, c, m;scanf("%d%d", &n, &m);while (m--){scanf("%d%d%d", &a, &b, &c);e[a].push_back(node(b, c));e[b].push_back(node(a, c));}// for (int i = 0; i <= n; i++)// {// dis[i] = INF;// }memset(dis, 0x3f, sizeof(dis));dis[1] = 0;// 優先隊列，隊頭元素最大，但是如果類型為struct需要重載<運算符q.push(node(1, dis[1]));dijkstra();for (int i = 1; i <= n; i++){printf("%d ", dis[i]);}system("pause");return 0; } void dijkstra() {while (!q.empty()){node x = q.top();q.pop();for (int i = 0; i < e[x.point].size(); i++){node y = e[x.point][i];if (dis[y.point] > dis[x.point] + y.value){dis[y.point] = dis[x.point] + y.value;q.push(node(y.point, dis[y.point]));}}} }

總結

以上是生活随笔為你收集整理的Dijkstra算法（c++版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。