如果有向图中边的权重是正整数时,可以优化
#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个点,边的权重为整数。估计最大路径为500。dijkstra用最小堆的时间复杂度ElogV\ E不能再优化,但是排序用的logV可以优化。既然权重是整数,则可以用桶排序的方法实现 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 的數目,也是最長的最短路徑長度。