//（只贴代码，不做讲解，欢迎纠正）
//用斐波那契堆实现优先队列 //复杂度O(VlogV+E) #include <iostream> #include <algorithm> #include <string.h> #include <string> #define INF 0x3F3F3F3F #define MAXSIZE 1001 using namespace std; int dis[MAXSIZE]; int path[MAXSIZE]; void dijkstra(int v, int start); void pathout(int from, int to); void graphin(int v, int e); struct node { int front, weight; node* next; }graph[MAXSIZE]; template<typename datatype> struct fib_node { fib_node() { degree = 0; parent = NULL; left = NULL; right = NULL; child = NULL; mark = false; } int degree; datatype key; fib_node<datatype> *parent, *left, *right, *child; bool mark; }; //最小堆 template<typename datatype> class fib_heap { public: fib_heap() { ssize = 0; root = NULL; } void push(fib_node <datatype>*x) { x->mark = false; if (ssize) { x->left = root; x->right = root->right; x->right->left = x; root->right = x; if (x->key<root->key) { root = x; } } else { root = x; x->right = x; x->left = x; } ssize++; } void push(datatype k) { fib_node <datatype>*x = new(fib_node<datatype>); x->key = k; this->push(x); } datatype top() { if (ssize) { return root->key; } throw string("in top(), the heap is empty"); } void unio(fib_heap<datatype> *h) { if (h->ssize == 0) return; if (this->ssize == 0) { root = h->root; this->ssize = h->ssize; return; } fib_node <datatype>*tmp = this->root->right; this->root->right = h->root->right; tmp->left = h->root; h->root->right = tmp; this->root->right->left = this->root; this->ssize += h->ssize; h->root = NULL; h->ssize = 0; } int size() { return ssize; } void pop() { if (!ssize) { throw string("in pop(), the heap is empty"); } fib_node<datatype> *now = root->child; while (now) { fib_node <datatype> *nex = now->right; now->right = root->right; now->left = root; root->right = now; now->right->left = now; now->parent = NULL; if (nex->parent == NULL) break; now = nex; } if (ssize == 1) { delete(root); root = NULL; } else { fib_node <datatype> *tmp = root; root->left->right = root->right; root->right->left = root->left; root = root->right; delete(tmp); conslidate(); } ssize--; } void decrease(fib_node<datatype> *x, datatype k) { if (x->key<k) throw(string("in decrease: the key of x is smaller than the new key!")); x->key = k; fib_node <datatype> *y = x->parent; if (y != NULL&&x->key<y->key) { cut(x, y); cascading(y); } if (x->key<root->key) { root = x; } } private: int ssize; void conslidate() { int D = -1; int tmp = ssize; while (tmp) { tmp >>= 1; D++; } ////////////////////////////////// fib_node <datatype>**deg = new(fib_node<datatype>*[D + 1]); memset(deg, 0, sizeof(deg)*(D + 1)); fib_node <datatype> *theend = root->left; fib_node <datatype> *now = root; while (true) { int d = now->degree; fib_node <datatype> *x = now; fib_node <datatype> *nex = now->right; while (deg[d]) { fib_node <datatype> *y = deg[d]; if (y->key<x->key) { swap(x, y); } //将y节点接到x节点的下面 y->right->left = y->left; y->left->right = y->right; y->parent = x; y->mark = false; if (x->child == NULL) { x->child = y; y->right = y; y->left = y; } else { y->right = x->child->right; y->left = x->child; x->child->right = y; y->right->left = y; } x->degree++; deg[d++] = NULL; } deg[d] = x; if (now == theend) break; now = nex; } root = NULL; for (int i = 0; i <= D; i++) { if (deg[i]) { if (root == NULL) { root = deg[i]; root->right = root; root->left = root; } else { deg[i]->left = root; deg[i]->right = root->right; root->right = deg[i]; deg[i]->right->left = deg[i]; if (deg[i]->key<root->key) { root = deg[i]; } } } } } void cut(fib_node<datatype> *x, fib_node<datatype> *y) { if (x->right == x) { y->child = NULL; } else { x->right->left = x->left; x->left->right = x->right; //防止y->child恰好为x y->child = x->right; } y->degree--; x->mark = false; x->right = root->right; x->left = root; root->right = x; x->right->left = x; x->parent = NULL; } void cascading(fib_node<datatype> *x) { fib_node <datatype> *y = x->parent; if (y) { if (!x->mark) { x->mark = true; } else { cut(x, y); cascading(y); } } } fib_node <datatype> *root; }; int main() { int start, v, e; cout << "请输入图(节点编号从0开始)：" << endl; cin >> v >> e; graphin(v, e); cout << "请输入起点：" << endl; cin >> start; dijkstra(v, start); for (int i = 0; i<v; i++) { if (i == start) continue; if (dis[i] == INF) continue; cout << "distance(" << start << "," << i << ") = " << dis[i] << " the path is: "; pathout(start, i); cout << endl; } return 0; } void graphin(int v, int e) { memset(graph, 0, sizeof(graph)); for (int i = 0; i<e; i++) { int from, to, w; cin >> from >> to >> w; node *tmp = graph[from].next; //用nex代替graph[from].next，节约时间 node *nex = new(node); graph[from].next = nex; nex->front = to; nex->weight = w; nex->next = tmp; } } struct point { point(int w_=0, int u_=0) { w = w_; u = u_; } int w, u; }; bool operator<(point a, point b) { return a.w < b.w; } //储存每个节点在堆中的位置，用于快速实现decrease-key操作 fib_node <point> *pinheap[MAXSIZE]; void dijkstra(int v, int start) { //bool vis[v]; bool *vis = new(bool[v]); fib_heap <point> unvis; int sizeunvis = v; memset(dis, 0x3F, sizeof(dis)); memset(path, 0xFF, sizeof(path)); memset(vis, 0x00, sizeof(vis)*v); dis[start] = 0; for (int i = 0; i<v; i++) { pinheap[i] = new(fib_node<point>); pinheap[i]->key = point(dis[i],i); unvis.push(pinheap[i]); } while (unvis.size()>0) { point heaptop = unvis.top(); unvis.pop(); int pmin = heaptop.u; vis[pmin] = true; for (node *p = graph[pmin].next; p != NULL; p = p->next) { int f = p->front; int sum = dis[pmin] + p->weight; if (dis[f]>sum) { dis[f] = sum; path[f] = pmin; if (!vis[f]) { unvis.decrease(pinheap[f], point(dis[f],f)); } } } } } void pathout(int from, int to) { if (from == to) { cout << from; return; } pathout(from, path[to]); cout << "->" << to; }
没有评论:
发表评论