Dijkstra简介

Dijkstra是用来求最短路的方法，朴素版Dijkstra适合稠密图，堆优化版Dijkstra算法适合稀疏图

朴素版Dijkstra

原题链接

整体思路就是从1点判断到n点，每次用当前点更新每个点的最小距离

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 550;

int n, m;

int dist[N];
int g[N][N];
bool st[N];

int Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));

    dist[1] = 0;

    for (int i = 0; i < n; i ++)
    {
        int t = -1;

        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                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()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);

    while (m --)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    }

    cout << Dijkstra() << endl;
}

本题自己在写代码时遇到的问题：

• dist数组表示每个点距离1点的距离
• g数组表示每两个点之间的距离
• st数组表示当前点有没有被更新过
• 在if (!st[j] && (t == -1 || dist[t] > dist[j]))这个条件中，!st[j] && (t == -1)好理解为什么这样写，但是对于dist[t] > dist[j]自己开始不知道为什么这样写，这是因为每个点的距离都是由当前遍历到的距离1最近的点更新得到的，如果不加这个条件就表示从1直接遍历到n，那么就会产生一种情况：假设5点距离1点的距离是3，4点距离1的距离是9，4点距离5的距离是5，那么在后面的点会被4点错误的更新如图，本来4的距离应该是1~2~3+4=7，结果现在成了1~2~4=7