在谈Dijkstra 算法

 稠密图，使用邻接矩阵存储，算法的时间复杂度是O(n^2), 使用邻接表，算法的时间复杂度是O(n^2 + m)。

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

每次需要从T集合中，找到路径最小的点，可以用最小堆优化，由于松弛操作，需要不断修改最小堆的值，这里需要手写堆才能实现，假如可以这么做，可以在O(1）时间找到最小值，由于需要对所有边做松弛操作，堆中总共有n个点，因此时间复杂度是mlogn。

但是实际操作中，我们使用STL的堆，每次松弛操作后，都将其插入到堆中，这样做会有冗余。总的复杂度是mlogm

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue, greater> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}