Dijkstra算法

单源最短路径算法，可以一次性求出源点u到其他所有点的最短路径。

算法思路：

将所有顶点分为已访问和未访问两类，初始时只有源点u是已访问的。
从未访问过的结点中找出与源点距离最近的点t，再遍历该点的邻接点，如果邻接点未被访问过，则判断能否用t来更新这个点的最短路径，如果可以，更新邻接点的最短路径和前驱结点。遍历完t的邻接点后，设置t为已访问状态。
以上步骤重复n轮，即可完成全部点的最短距离和前驱结点更新。

为了实现Dijkstra算法，需要以下额外变量用以记录状态：

dist数组：dist[i]表示顶点i到源点的最短距离，初始时只有源点和与源点直接相邻的点有数值，其他点为无穷大。
visited数组：记录顶点是否被访问过。
p数组：p[i]表示i到源点的最短路径上的前一跳，初始时只有源点和与源点直接相邻的点有数值，其他点为-1。

如果只需要求最短路径距离的值，不需要关注到底是哪一条路径，则可以省略p数组。

Dijkstra算法本质是贪心算法，每一步都是当前状态的最优解。

以下是朴素版本的Dijkstra算法实现：

#define MAXN 1005
#define INF 0x3f3f3f3f

int G[MAXN][MAXN];  // 邻接矩阵，G[u][v]表示顶点u到顶点v的距离，或者为INF，表示u、v之间不存在边
int n;              // 顶点数

int dist[MAXN];     // dist[i]表示顶点i到源点的最短距离，初始时只有源点和与源点直接相邻的点有数值，其他点为INF
int p[MAXN];        // p[i]表示i到源点的最短路径上的前一跳，初始时只有源点和与源点直接相邻的点有数值，其他点为-1
int visited[MAXN];  // 表示顶点i是否已访问过

void dijkstra(int u) { // 计算源点u到其他各点的最短距离
    // 初始化
    for(int i = 0; i < n; i++) {
        visited[i] = false;
        dist[i] = G[u][i]; // 初始化源点到其他各顶点的距离，可能为INF
        p[i] = (dist[i] == INF ? -1 : u); // 与源点相邻，设置前驱结点为u，不相邻，设置前驱结点为-1
    }

    // 从源点u开始
    dist[u] = 0;
    visited[u] = true;

    // 对所有顶点进行松弛操作
    for(int i = 0; i < n; i++) {
        // 找出剩余顶点中离源点最近的点
        int tmp = INF, t = u;
        for(int j = 0; j < n; j++) {
            if(!visited[j] && dist[j] < tmp) {
                t = j;
                tmp = dist[j];
            }
        }
        if(t == u) return;
        visited[t] = true;
        for(int j = 0; j < n; j++) { // 更新t的邻接点的最短路径长度，松弛操作
            if(G[t][j] != INF && !visited[j] && dist[j] > dist[t] + G[t][j]) {
                dist[j] = dist[t] + G[t][j];
                p[j] = t;
            }
        }
    }
}

以上算法复杂度为O(n²)，可以利用优先队列进行优化，将寻找距离最短的未访问顶点这一步缩减到O(logn)的复杂度，示例代码如下：

#define MAXN 1005
#define INF 0x3f3f3f3f

int G[MAXN][MAXN]; // 邻接矩阵，G[u][v]表示顶点u到顶点v的距离，或者为INF，表示u、v之间不存在边
int n;             // 顶点数

int dist[MAXN];    // dist[i]表示顶点i到源点的最短距离，初始时只有源点和与源点直接相邻的点有数值，其他点为INF
int p[MAXN];       // p[i]表示i到源点的最短路径上的前一跳，初始时只有源点和与源点直接相邻的点有数值，其他点为-1
int visited[MAXN]; // 表示顶点i是否已访问过

struct Node {
    int u;
    int dis;
    Node() {}
    Node(int _u, int _dis) : u(_u), dis(_dis) {}
    bool operator<(const Node &other) const { return dis > other.dis; } // 重载<， dis越小优先级越高
};

void dijkstra(int u) { // 计算源点u到其他各点的最短距离
    priority_queue<Node> que;
    // 初始化
    for(int i = 0; i < n; i++) {
        visited[i] = false;
        dist[i] = G[u][i]; // 初始化源点到其他各顶点的距离，可能为INF
        p[i] = (dist[i] == INF ? -1 : u); // 与源点相邻，设置前戏结点为u，不相邻，设置前驱结点为-1
    }

    // 从源点u开始，注意这里没有设置u为已访问状态
    dist[u] = 0;
    que.push({u, 0});

    // 对所有顶点进行松弛操作
    for(int i = 0; i < n; i++) {
        Node it = que.top();
        que.pop();
        int t = it.u;
        if(visited[t]) continue;
        visited[t] = true;
        for(int j = 0; j < n; j++) { // 更新t的邻接点的最短路径长度，松弛操作
            if(G[t][j] != INF && !visited[j] && dist[j] > dist[t] + G[t][j]) {
                dist[j] = dist[t] + G[t][j];
                p[j] = t;
                que.push({j, dist[j]});
            }
        }
    }
}

Floyd算法

任意两点间最短路径算法，可以处理负权边，但不能处理存在负权环的图。

Floyd算法的思路是对图中任意的两个结点，枚举剩余所有的点，看能不能用剩余的点来更新当前这两个点的距离。枚举任意两个点的时间复杂度为O(n²)，再枚举剩余的所有点，时间复杂度为O(n)，所以Floyd算法总的时间复杂度为O(n³)。

Floyd算法的本质是动态规划。

算法步骤：

使用邻接矩阵G[][]来存储图，使用dist[i][j]来表示i到j的最短距离，使用p[i][j]来表示i到j最短路径上j的前一跳。
初始化。dist[i][j] = G[i][j]，如果结点i到结点j有边相连，则p[i][j] = i，否则p[i][j] = -1。
枚举所有的i、j，然后在中间插入节点k，看是否可以缩短节点i、j之间的距离。如果dist[i][j]>dist[i][k]+dist[k][j]，则dist[i][j]=dist[i][k]+dist[k][j]，并记录节点j的前驱为p[i][j] = p[k][j]。

示例代码：

#define MAXN 1005
#define INF 0x3f3f3f3f

int G[MAXN][MAXN]; // 邻接矩阵，G[u][v]表示顶点u到顶点v的距离，或者为INF，表示u、v之间不存在边
int n;             // 顶点数

int dist[MAXN][MAXN]; // dist[i][j]表示顶点i到j的最短距离
int p[MAXN][MAXN];    // p[i][j]表示i到j的最短路径上j的前一跳，如果不存在，则为-1

void floyd() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            dist[i][j] = G[i][j]; // 隐含i==j时dist[i][j]为0，以及i,j不相连时dist[i][j]为INF
            if(i != j && dist[i][j] != INF) {
                p[i][j] = i;
            } else {
                p[i][j] = -1;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                if(dist[i][k] + dist[k][j] < dist[i][j]) {
                    // 从i经k到j的路径更新，更新dist和p
                    dist[i][j] = dist[i][k] + dist[k][j];
                    p[i][j] = p[k][j];
                }
            }
        }
    }
}

页面树结构

最短路径

Dijkstra算法

Floyd算法