戴克斯特拉+斐波那契堆

//（只贴代码，不做讲解，欢迎纠正）

//用斐波那契堆实现优先队列 
//复杂度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;
}