图论之最短路算法

Floyd

#include <cstdio>
待补坑

Dijkstra

朴素o(n^2)

int n, m;// 点数量以及边数量
int w[MAXN][MAXN];// 记录任意两点之间距离
int d[MAXN];// 点的权值
int v[MAXN];// 标记数组
void Dijkstra() {
    // 初始化所有点权为INF
    for(int i=2; i<=n; i++) d[i] = INF;

    for(int i=1; i<=n; i++) {
        int x, m = INF;
        // 选出相连的d值最小的点
        for(int y=1; y<=n; y++) if(!v[y] && d[y]<=m) m = d[x=y];
        // 标记此点为已访问
        v[x] = true;
        // 更新最小d值
        for(int y=1; y<=n; y++) {d[y] = min(d[y], d[x] + w[x][y]);}

    }
}