朴素Dijkstra求单源正权边稠密图最短路思路 o(n^2)

1.由于本题存在重边，所以我们用g[a][b]存储a到b的边长时一定要取一个最小值
2.将所有点到源点的距离赋为正无穷，同时点1到源点距离赋为0
3.找出当前未被确定距离的所有点中到源点距离最小的点，并确定该点距离就是最短距离
4.利用该点到源点的距离和g数组去更新一遍所有点到源点的距离
5.循环n次，每一次确定一个点

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

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

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

    for (int i = 1; i <= n; i ++ )              // 每次确定一个点，一共要确定n次
    {
        int t = 0;

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

        st[t] = true;

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


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

    return dist[n];
}

int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    while (m -- )
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    }

    cout << dijkstra() << endl;

    return 0;
}

利用堆排序优化的Dijkstra算法求单源正权稀疏图最短路思路 o(mlogn)

1.用邻接表将图储存下来
2.将所有点距源点赋为无穷，1距源点赋为0
3.创建小根堆，每次取出堆顶元素，如果没有被标记过则确定其最短距离并对其进行标记，被标记过则忽略掉
4.遍历链表，对其中元素的最短距离进行更新，并更新过后的元素加入小根堆中
5.堆遍历次数为直到堆空为止，因为堆中会有冗余元素加入，所以我们并不能确定其遍历次数

思考过后的两个问题

如何过滤掉重边？
这里是根据邻接表的存储特性进行过滤的，所有重边都会被存储在一条链表中，当遍历一个元素的所有出边时会自动更新为最短路径

为什么不进行标记也可以AC？
每次取出一个点后，那么该点的最短路径就已经确定了，所以后续该点一定不会被加入堆中，但是如果在该点被第一次取出之前，可能会有多个不同dist的该点被加入到堆中，当然，最小的dist的点一定是先出堆的，这时该点的最短路径已经确定了，剩余的该点备份也会出堆，但是由于dist较大，所以最短距离是不会被更新的，对结果没有影响但会浪费时间

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 150010;

int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
int n, m;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; 
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});              // 按照first进行排序，所以到源点的距离必须在前面
    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] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

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

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m -- )
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }

    cout << dijkstra() << endl;

    return 0;
}