如果有向圖中邊的權(quán)重是正整數(shù)時，可以優(yōu)化

#include <iostream> #include <limits> #include <algorithm> #include <vector>using namespace std;int w[9][9]; int d[9];//記錄每個點到點S的最短路徑 int parent[9];//記錄路徑 bool visit[9];struct Node {int to;int from; };vector<list<Node> > bucket(500); //圖中有9個點，邊的權(quán)重為整數(shù)。估計最大路徑為500。dijkstra用最小堆的時間復雜度ElogV\ E不能再優(yōu)化，但是排序用的logV可以優(yōu)化。既然權(quán)重是整數(shù)，則可以用桶排序的方法實現(xiàn)void dial(int source) {memset(visit,0,sizeof(visit) );bucket[0].push_back( Node( source, source) );int v = 0;int slot = 0;for (; v<9 && slot <500; ++v) {while (slot < 500 && bucket[slot].empty()) ++slot;//找到一個到源端最小的點if (slot == 500)break;Node tnode = bucket[slot].front();if (visit[tnode.to])continue;bucket[slot].pop_front();d[tnode.to] = slot;parent[tnode.to] = tnode.from;visit[tnode.to] = true;for (int i = 0; i < 9 ; ++i) {if ( i != tnode.to && !visit[i] && w[tnode.to][i]) {bucket[slot + w[tnode.to][i]].push_back(Node(tnode.to,i));}}} }int main() {}
參考自 http://www.csie.ntnu.edu.tw/~u91029/Path.html

整個 bucket 最多放入 E 個點、拿出 E 個點，然後整個 bucket 讀過一遍，時間複雜度總共是 O(E+W) ，其中 W 為 bucket 的數(shù)目，也是最長的最短路徑長度。

總結(jié)

以上是生活随笔為你收集整理的dijkstra算法优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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