dijkstra图示

因为之前已经介绍过了,现在就不仔细介绍了,直接上算法。

朴素版

st的最短距离算法流程:

b[]表示当前已经确定最短距离的点。

  1. dis[s] = 0, dis[其他] = +∞
  2. for (int i = 1; i <= n; i ++)

    • t:不在b中的最短距离的点
    • t加入b[]
    • 使用t更新其他未被确定的点的距离

代码实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 510;

int n, m;
int w[N][N];
int dis[N];
bool b[N];


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

    for (int i = 0; i < n; i ++) {
        int k = -1;
        for (int j = 1; j <= n; j ++)
            if (!b[j] && (k == -1 || dis[k] > dis[j]))
                k = j;

        b[k] = true;

        for (int j = 1; j <= n; j ++) {
            dis[j] = min(dis[j], dis[k] + w[k][j]);
        }
    }

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

int main() {
    scanf("%d %d", &n, &m);

    memset(w, 0x3f, sizeof w);

    while (m --) {
        int i, j, k;
        scanf("%d %d %d", &i, &j, &k);
        w[i][j] = min(w[i][j], k);
    }

    int t = dijkstra();

    printf("%d", t);
    return 0;
}

堆优化版

最后修改:2022 年 02 月 27 日
如果觉得我的文章对你有用,请随意赞赏