Dijkstra 算法

将结点分成两个集合：已确定最短路长度的点集（记为$S$ 集合）的和未确定最短路长度的点集（记为$T$ 集合）。一开始所有的点都属于$T$集合。初始化$dis(s) = 0$，其他点的均为$INF$。

然后重复这些操作：

  1. 从 $T$ 集合中，选取一个最短路长度最小的结点，移到 $S$ 集合中。
  2. 对那些刚刚被加入 $S$ 集合的结点的所有出边执行松弛操作。

直到 $T$ 集合为空，算法结束。

暴力：

不使用任何数据结构进行维护，每次 2 操作执行完毕后，直接在 $T$ 集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为$O(m)$ ，1 操作总时间复杂度为$O(n^2)$ ，全过程的时间复杂度为 $O(n^2)$。

struct edge {
    int v, w;
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];

void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0, mind = 0x3f3f3f3f;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dis[j] < mind)
                u = j, mind = dis[j];
        vis[u] = true;
        for (auto ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w)
                dis[v] = dis[u] + w;
        }
    }
}
// 邻接矩阵
#define N 505
#define INF 0x3f3f3f3f
int g[N][N]; // memset(g, 0x3f, sizeof(g));
int dis[N], vis[N];
void dijkstra(int n, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = 0, mind = INF;
        for (int j = 0; j < n; j++)
            if (!vis[j] && dis[j] < mind)
                u = j, mind = dis[j];
        vis[u] = 1;
        for (int v = 0; v < n; v++) {
            if (v == u) continue;
            if (dis[v] > dis[u] + g[u][v])
                dis[v] = dis[u] + g[u][v];
        }
    }
}

优先队列：

和二叉堆类似，但使用优先队列时，如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是 $O(m)$ 的，时间复杂度为 $O(mlogm)$。

struct edge {
    int v, w;
};

struct Node {
    int dis, u;
    bool operator<(const Node& o) const { return dis > o.dis; }
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<Node> q;

void dijkstra(int n, int s) {
    memset(dis, 63, sizeof(dis));
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto ed : e[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}

Floyd 算法

多源最短路，求任意两个结点之间的最短路。时间复杂度$O(n^3)$，常数小。

其思想是动态规划。

设图中共n个节点，节点编号从0到n-1。

定义f[k][x][y]，表示只允许经过节点 0 到 k-1，节点 x 到节点 y 的最短路长度。

初始化f[0][][]：