写在前面：
今天我们来看看图论中另一个非常重要的问题 —— 最短路径，正如其名就是要再图中找到起点到终点的最短路径，这就需要不断地去比较每条边的权值。
这一讲我们将会具体介绍迪杰斯特拉算法和弗洛伊德算法的实现。

迪杰斯特拉算法

迪杰斯特拉算法是一个单源点的一个最短路径算法，也就是说，我们这个算法会求得从一个顶点到其所有顶点的最短路径。

这个算法需要用到邻接矩阵来存储所有边值，并且需要一个辅助数组来更新最短路径，需要一个路径数组存储最短路径的结点，还需要一个状态数组来判断当前结点是否已经加入最短路径。

这样说可能会有点晕，我们还是先来看图，假设有这样一张图：

现在，我们要找到结点 0 到结点 8 的最短路径，步骤如下：

辅助数组 D：存储结点 0 到当前结点的最短路径权值。
路径数组 P：存储当前最短路径到该点的父结点。
状态数组 Final ：记录当前结点是否已经加入到最短路径当中（0 代表还没有加入，1 代表已经加入）。

第一步：初始化我们上述提到的三个数组，将结点 0 加入数组中，并更新辅助数组即结点 0 连出去的边的权值。

第二步：找到当前辅助数组中的边权最小值，即结点 0 到结点 1 ，故加入结点 1 ，并且更新结点 1 连出去的边值。
可以发现之前更新过结点 2 的辅助数组，现在又需要更新，因为结点 0 到结点 2 的最短路径不再是 0 -> 2 ，而是 0 -> 1 -> 2 ，即最短路径值从 5 变为 1+3 = 4 ，并且结点 2 的 P 不再是 0 ，它在最短路中要先经过结点 1 ，故 P 改成 1 。

第三步：更上面一样，找到结点 2 加入最短路，并且更新。

第四步：找到结点 4 加入最短路，并且更新。

第五步：找到结点 3 加入最短路，并且更新。

第六步：找到结点 5 加入最短路，并且更新。

第七步：找到结点 6 加入最短路，并且更新。

第八步：找到结点 7 加入最短路，并且更新。

第九步：到达终点，生成最短路径。

全部代码

#include <bits/stdc++.h>
using namespace std;
#define MaxVertices 100    //假设包含的最大结点数
#define MaxWeight 99999    //假设两点不邻接的正无穷值

/*
9
16
0 1 1
0 2 5
1 2 3
1 3 7
1 4 5
2 4 1
2 5 7
3 4 2
4 5 3
3 6 3
4 6 6
4 7 9
5 7 5
6 7 2
6 8 7
7 8 4
*/

//定义邻接矩阵
struct AdjMarix {
    int Edge[MaxVertices][MaxVertices] = { 0 };
    int numV;    //当前顶点的个数
    int numE;    //当前边的个数
};

//构建图
void CreatGraph(AdjMarix *G) {
    int vi, vj, w;
    cout << "请输入顶点数量：" << endl;
    cin >> G->numV;
    for (int i = 0; i < G->numV; i++) {
        for (int j = 0; j < G->numV; j++) {
            G->Edge[i][j] = MaxWeight;
        }
    }
    cout << "请输入边的数量：" << endl;
    cin >> G->numE;
    cout << "请输入边的信息：" << endl;
    for (int i = 0; i < G->numE; i++) {
        cin >> vi >> vj >> w;
        G->Edge[vi][vj] = w;
        G->Edge[vj][vi] = w;
    }
}

//迪杰斯特拉算法
void Dijkstra(AdjMarix &M, int v0, int *P, int *D) {
    //初始化
    int Final[MaxVertices] = { 0 };
    for (int i = 0; i < M.numV; i++) {
        P[i] = -1;
        D[i] = M.Edge[v0][i];
    }
    //加入结点V0
    D[v0] = 0;
    Final[v0] = 1;
    
    int k = v0;
    for (int i = 0; i < M.numV; i++) {
        int MIN = MaxWeight;    //找到目前数组中权值最小的一条边
        for (int j = 0; j < M.numV; j++) {
            if (Final[j] == 0 && D[j] < MIN) {
                MIN = D[j];
                k = j;
            }
        }
        Final[k] = 1;    //标记该结点已经加入最短路径中
        for (int w = 0; w < M.numV; w++) {
            if (Final[w] == 0 && (MIN + M.Edge[k][w] < D[w])) {
                D[w] = MIN + M.Edge[k][w];    //更新最小值
                P[w] = k;    //记录路径（说明最短路径中到w的要经过k）
            }
        }
    }
}

int main() {
    AdjMarix AM;
    CreatGraph(&AM);
    int P[MaxVertices], D[MaxVertices];
    Dijkstra(AM, 0, P, D);
    cout << "V0到各个结点的最短路径：" << endl;
    for (int i = 0; i < AM.numV; i++) {
        cout << "V" << i << "：";
        int j = i;
        while (j != -1) {
            cout << "V" << j << "->";
            j = P[j];
        }
        cout << "V0    【最短路径为" << D[i] << "】" << endl;
    }
}

弗洛伊德算法

这个算法相对于上一个就十分暴力了，直接三层循环，遍历所有情况，每次都去试图找到一个中间结点，判断是否能使结点 i 到结点 j 经过结点 k 能缩短路径长度。这里我就直接展示代码啦，因为实质算法三层循环就搞定了。

#include <bits/stdc++.h>
using namespace std;
#define MaxVertices 100    //假设包含的最大结点数
#define MaxWeight 99999    //假设两点不邻接的正无穷值

/*
9
16
0 1 1
0 2 5
1 2 3
1 3 7
1 4 5
2 4 1
2 5 7
3 4 2
4 5 3
3 6 3
4 6 6
4 7 9
5 7 5
6 7 2
6 8 7
7 8 4
*/

//定义邻接矩阵
struct AdjMarix {
    int Edge[MaxVertices][MaxVertices] = { 0 };
    int numV;    //当前顶点的个数
    int numE;    //当前边的个数
};

//创建图
void CreatGraph(AdjMarix *G) {
    int vi, vj, w;
    cout << "请输入顶点数量：" << endl;
    cin >> G->numV;
    for (int i = 0; i < G->numV; i++) {
        for (int j = 0; j < G->numV; j++) {
            if (i == j) {
                G->Edge[i][j] == 0;
            } else {
                G->Edge[i][j] = MaxWeight;
            }
        }
    }
    cout << "请输入边的数量：" << endl;
    cin >> G->numE;
    cout << "请输入边的信息：" << endl;
    for (int i = 0; i < G->numE; i++) {
        cin >> vi >> vj >> w;
        G->Edge[vi][vj] = w;
        G->Edge[vj][vi] = w;
    }
}

//弗洛伊德算法
void Floyd(AdjMarix &M, int P[][MaxVertices], int D[][MaxVertices]) {
    for (int i = 0; i < M.numV; i++) {
        for (int j = 0; j < M.numV; j++) {
            P[i][j] = j;
            D[i][j] = M.Edge[i][j];
        }
    }
    //遍历所有结点所有边并更新，找到最短路径
    for (int i = 0; i < M.numV; i++) {
        for (int j = 0; j < M.numV; j++) {
            for (int k = 0; k < M.numV; k++) {
                int temp = (D[j][i] == MaxWeight || D[i][k] == MaxWeight) ? MaxWeight : D[j][i] + D[i][k];
                if (temp < D[j][k]) {
                    D[j][k] = temp;
                    P[j][k] = P[j][i];
                }
            }
        }
    }
    cout << "最小路径：" << endl;
    for (int i = 0; i < M.numV; i++) {
        for (int j = 0; j < M.numV; j++) {
            cout << P[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    cout << "最小路径值：" << endl;
    for (int i = 0; i < M.numV; i++) {
        for (int j = 0; j < M.numV; j++) {
            printf("%2d ", D[i][j]);
        }
        cout << endl;
    }
}

int main() {
    AdjMarix AM;
    CreatGraph(&AM);
    int P[MaxVertices][MaxVertices], D[MaxVertices][MaxVertices];
    Floyd(AM, P, D);
}

如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~