2016-08-17

Dijkstra算法的最小堆优化

关于Dijkstra算法的具体步骤可以参考关于最短路径的几个算法
Dijkstra算法里面每次找出离源点最近之点，使用了两个嵌套的循环语句。导致时间复杂度为O(N^2)。
本例通过最小堆，优化这两个嵌套的循环语句。令算法整体复杂度降为O(NlogN)。

实现代码

#include<stdio.h>
// book记录那些顶点已经放入生成树中
int dis[8];
// h用来保存堆，pos用来存储每个顶点再堆中的位置，size为堆的大小
int h[7], pos[7], size;
int n=6, m=9,k;
int inf = 99999999;
int i, j;
int u[10], v[10], w[10];
int first[7], next[10];
void swap(int x, int y)
{
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
    t = pos[h[x]];
    pos[h[x]] = pos[h[y]];
    pos[h[y]] = t;
}
//传入一个需要向下调整的顶点编号
void siftdown(int i)
{
    int t, flag = 0;
    while (i * 2 <= size&&flag == 0)
    {
        // 首先判断左儿子
        if (dis[h[i]] > dis[h[i * 2]])
            t = i * 2;
        else
            t = i;
        // 判断右儿子
        if (i * 2 + 1 <= size)
        {
            // 如果右儿子的值更小
            if (dis[h[t]]>dis[h[i * 2 + 1]])
                t = i * 2 + 1;
        }
        // 若无须交换，也就是子树满足最小堆
        if (t != i)
        {
            swap(t, i);
            i = t;
        }
        else
            flag = 1;
    }
}
void siftup(int i)
{
    int flag = 0;
    if (i == 1) return;
    while (i != 1 && flag == 0)
    {
        // 判断父节点
        if (dis[h[i]]<dis[h[i / 2]])
            swap(i, i / 2);
        else
            flag = 1;
        i = i / 2;
    }
}
int pop()
{
    int t;
    t = h[1];
    h[1] = h[size];        //将堆的最后一个点赋值到堆顶
    pos[h[1]] = 1;
    size--;
    siftdown(1);
    //pop顶点编号出来
    return t;
}
int main()
{
    int count = 0;
    for (i = 1; i <= m; i++)
        scanf("%d %d %d", &u[i], &v[i], &w[i]);
    // 初始化dis
    dis[1] = 0;
    for (i = 2; i <= n; i++)    dis[i] = inf;
    // 邻接表
    for (i = 1; i <= n; i++) first[i] = -1;
    for (i = 1; i <= m; i++)
    {
        next[i] = first[u[i]];
        first[u[i]] = i;
    }
    count++;
    k = first[1];
    // 遍历邻接表。找出离顶点1相邻点的权值，放入dis中
    while (k != -1)
    {
        dis[v[k]] = w[k];
        k = next[k];
    }
    // 初始化堆
    size = n;
    for (i = 1; i <= size; i++){ h[i] = i; pos[i] = i; }
    //生成最小堆
    for (i = size / 2; i >= 1; i--){ siftdown(i); }
    pop();
    while (count < n)
    {
        j = pop();
        count++;
        // 遍历以顶点j开头的所有边
        // k=为第n条边
        k = first[j];
        while (k != -1)
        {
            if (dis[v[k]]>dis[u[k]] + w[k])
            {
                dis[v[k]] = dis[u[k]] + w[k];
                siftup(pos[v[k]]);
            }
            k = next[k];
        }
    }
    for (i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}