其实按照萨尼的《数据结构、算法与应用》中的说法
这两种实现方式都用到了优先队列。
这里只是选择使用list链表（严格来说应该叫做“无序链表”）实现优先队列还是选择使用堆来实现时优先队列的区别。

使用list的实现

第一个是使用list实现的。
复杂度是O(n^2)

基于list的复杂度分析

每次从链表中取得并删除最小的值需要O(n);对于整个程序而言该操作执行O(n)次所以是O(n*n)为：
O(n^2)
对于更新操作。因为一个图有n个顶点。对于每个顶点都需要检查更新它邻接点们每次更新需要扫一遍链表O(n);这里的扫一遍包含更改d[j]，但是更新d[j]时间为theta(1)。所以总的为O(n^2);

template <class T>
void graph<T>:: dj(int source, int p[], int d[]) {
    if (source < 1 || source > n)return; //如果越界，直接退出
    //下面先进行初始化操作。
    list<int> newreachablevertices;
    for (int i = 1; i <= n; ++i)
    {   d[i] = a[source][i];
        if (a[source][i] != noEdge) {
            newreachablevertices.push_back(i);
            p[i] = source;
        }
        else
            p[i] = -1;
    }
    p[source] = 0;
    //下面进行更新
    while (!newreachablevertices.empty()) {
        list<int>::iterator it;//使用迭代器找到d值最小的
        it = newreachablevertices.begin();
        int v = *it;
        it++;
        while (it != newreachablevertices.end()) {
            if (d[*it] < d[v])
                v  = *it;
            it++;
        }
        //找到最小值d对应的点v了
        //下面使用迭代器删除这个点
        list<int>::iterator iter;//使用迭代器找到d值最小的
        for (iter = newreachablevertices.begin(); iter != newreachablevertices.end(); ++iter)
            if (*iter == v)
                iter = newreachablevertices.erase(iter);
        for (int j = 1; j <= n ; ++j)
            if (a[v][j] != noEdge && (p[j]==-1 || d[j] > d[v] + a[v][j]))
            {
                d[j] = d[v] + a[v][j];
                if (p[j] == -1)
                    newreachablevertices.push_back(j);
                p[j] = v;
            }
    }
    for (int i = 1; i <= n; ++i)
        cout << p[i] << endl;               //输出各个点的前导
}

实际应用

HDU2544

#include <iostream>
#include <list>
using namespace std;
int n = 110; //顶点数
int m = 10000; //边数
int a[110][110];//邻接矩阵
int noEdge = 99999999;    
int p[110];  //p与d都不用初始化，因为dj中会初始化
int d[110];
void dj(int source) {
    if (source < 1 || source > n)return; //如果越界，直接退出
    //下面先进行初始化操作。
    list<int> newreachablevertices;
    for (int i = 1; i <= n; ++i)
    {   d[i] = a[source][i];
        if (a[source][i] != noEdge) {
            newreachablevertices.push_back(i);
            p[i] = source;
        }
        else
            p[i] = -1;
    }
    p[source] = 0;
    //下面进行更新
    while (!newreachablevertices.empty()) {
        list<int>::iterator it;//使用迭代器找到d值最小的
        it = newreachablevertices.begin();
        int v = *it;
        it++;
        while (it != newreachablevertices.end()) {
            if (d[*it] < d[v])
                v  = *it;
            it++;
        }
        //找到最小值d对应的点v了
        //下面使用迭代器删除这个点
        list<int>::iterator iter;//使用迭代器找到d值最小的
        for (iter = newreachablevertices.begin(); iter != newreachablevertices.end(); ++iter)
            if (*iter == v)
                iter = newreachablevertices.erase(iter);
        for (int j = 1; j <= n ; ++j)
            if (a[v][j] != noEdge && (p[j] == -1 || d[j] > d[v] + a[v][j]))
            {
                d[j] = d[v] + a[v][j];
                if (p[j] == -1)
                    newreachablevertices.push_back(j);
                p[j] = v;
            }
    }
    cout << d[n] << endl;
}
int main(int argc, char const *argv[])
{
    int source  = 1;
    while (1) {
        cin >> n >> m;
        if (n == 0 && m == 0)
        {
            break;
        }
        for (int i = 0; i < 110; ++i)
        {

            for (int j = 0; j < 110; ++j)
            {
                a[i][j] = noEdge;
            }
        }
        int aa, b , c;
        for (int i = 0; i < m; ++i)
        {
            cin >> aa >> b >> c;
            a[aa][b] = c; //如果是无向图那么两个方向都要设置一下
            a[b][aa] = c;
        }
        dj(1);

    }
    return 0;
}

使用heap堆的实现

也是直接上代码
分析后可以发现其实使用heap实现的dj算法不如链表快
这主要是由于heap更新操作耗时长带来的结果
其实在每次取最小值时heap要快于链表。

基于heap的复杂度分析

对于步骤：弹出newreachablevertices中d[i]最小的i。
每次弹出i为O（logn）对于整个程序而言该步骤执行O（n）时间所以为O（nlogn）
对于更新d[j]操作：有两种思路如果是基于数组自实现的小根堆那么从后往前扫，边扫边更新维护heap，此时为nlogn；
因为该步骤也是执行n次（因为上一步取出i最多取n次）
所以是O(n^2logn)