最短路径 分为 单资源最短路径 和 两点间最短路径 ，其分别采用Dijkstra(迪杰斯特拉)、Floyd(弗洛伊德)算法来实现。

迪杰斯特拉算法(Dijkstra)

即：一个顶点到其他任意顶点的最短距离

如下图所示，为A、B、C、D、E之间的路径图

使用Dijkstra算法若想求出他们之间的最短路径，需要找到该顶点到其他顶点中距离最短的，然后该“最短顶点”(最短边)，不停的更新到其他顶点的最短距离，然后加入新的“最短顶点”，在更新到其他顶点的最短距离，知道最后，即求出该点到其他顶点的最短路径。

注意：通过上述步骤，是不是感觉有点像最小生成树的prim(普里姆算法)的求解过程呢

下面就以A节点为例，求出到其他节点的最短路径

1.首先，先假设A点到其他点的直线距离为最短路径，A加入到集合N中(下次不再对其更新最短)，默认如下

2.对比A节点到其他节点之间的路径，取最短，这里为A-B，将B加入到集合N中；并且从B点开始对比到集合N外的其他顶点的距离，如果(A-B边) 与 (B到其他顶点) 距离只和小于 A顶点距离直接其他顶点距离，那么更新最短距离为B到其他顶点距离 + （A-B）距离之和，如下所示

3.上一轮，通过B更新到其他顶点距离的过程，可以顺道将B点到其他顶点之间的最短的一边找到，为B-C,将C加入集合N中，此时任和步骤2一样，对比c到N集合外的顶点距离，与之前更新过的最短距离进行对比，如果更短则更新距离和上一个节点(此时集合外只剩下D、E)，否则不变，结果如下所示

4.通过上一轮，通过C更新到其他顶点距离的过程，找到C到其他顶点的最短边，为C-E，将E加入集合N中，此时和步骤2、3一样，对比E到N集合外的顶点距离，与之前更新过的最短距离进行对比，如果更短则更新距离和上一个节点(此时集合外只剩下D了)，结果如下所示

5.此时到所有节点的最短路径已经更新完毕了，则这个结果即为单资源最短路径了

由于上面结果保存的为目的节点和上一个节点，其实如果想寻找全路径，那么只需要通过preNode一直向前，直到preNode为A即可，然后从前向后遍历即为完整路径了

一、代码实现跟前面的案例很像，

先声明保存结果的边集数组

typedef struct {
    int preNode; //上一个节点
    int node; //目的节点
    int weight; //路径长度或者权值
} LSLineNode; //临边数组基本结构，只不过先、后用名字，在这里使用更为直白
单资源最短路径实现步骤如下：
1.声明到其他路径最短边距离为min，其顶点索引为m，结果数组为nodes，是否已经作为最短路径集合flag
2.找到指定顶点V，到其他顶点中最小的边，保存路径到集合nodes中，作为默认结果，并且记录最小值和和其索引
3.将顶点V和最小顶点m，标记为1，意思是加入了集合N
4.开始遍历
5.如果在flag为1(在集合N内)，continue跳过进入下一轮，否则进行下一步
6.从最小顶点开始加上距离其他顶点的距离，查看其和是否比前面求出的最短路径更短，如果更短则更新值和preNode，否则不更新；并且找出此过程最短边，找出最小顶点，以便后续使用
7.更新最小顶点，最短边初始为最大值，以便以下一轮更新最短路径，将最小顶点flag标记为1
8.变量自增，进入下一轮步骤5，直到循环结束，即：所有顶点都加入集合N中
//迪杰斯特拉算法来解决，找到最短边，在通过最短边更新其他的最短边，依次递推，最短路径点从默认集合N,到最短路径集合S,逐步更新，与prim算法很像
void showSingleMinShortPathByDijkstra(int v) {
    v--; //这里按照索引用，减1来对应
    int m = 0, min = MAXINT;
    int flag[N] = {0};//标志数组，标识顶点是否已经加入进去了
    LSLineNode nodes[N]; //保存结果数组（从指定顶点v到顶点N的路径信息）
    //给予结果数组初值，并找出最小的边
    for (int i = 0; i < N; i++) {
        nodes[i].weight = linesList[v][i];
        nodes[i].node = i;
        nodes[i].preNode = v;
        if (nodes[i].weight < min) {
            m = i;
            min = nodes[i].weight;
    flag[v] = 1; //默认资源边已经加入
    flag[m] = 1; //将最小的边放入S(flag)集合，置标志位即可
    min = MAXINT; //初始化最大值，用于更新最小值
    for (int i = 0; i < N; i++) {
        int temM = 0; //保存m的更新的最小是值，用于下一轮更新最短路径，避免m在此次循环被覆盖
        for (int j = 0; j < N; j++) {
            //已经加入S集合的点不做处理
            if (flag[j] != 0) continue;
            //开始加入新的节点进行尝试，是否存在最短路径，然后逐步迭代
            if (nodes[m].weight + linesList[m][j] < nodes[j].weight) {
                nodes[j].preNode = m;
                nodes[j].weight = nodes[m].weight + linesList[m][j];
            if (nodes[j].weight < min) {
                temM = j;
                min = nodes[j].weight;
        m = temM;
        flag[m] = 1;
        min = MAXINT;
    //此时的LSLineNode nodes即为最短路径
    printResult(nodes, v);
二、上面获取到的结果，会发现有preNode，无法直接获取指定顶点到其他顶点的完成路径
由于存在preNode，即上个节点，可以通过循环查找，直到preNode为指定顶点为止，然后正序遍历直到当前顶点即可
//最短路径的获取方式通过查找preNode来查找经过路径，为0时结束,打印出来即可
void printResult(LSLineNode *nodes, int v) {
    printf("\n迪杰斯特拉:\n");
    for (int i = 0; i < N; i++) {
        int result[N] = {nodes[i].node + 1, 0};
        int j = i, k = 1;
        if (i != v) {
            while (nodes[j].preNode != v) {
                result[k++] = nodes[j].preNode + 1;
                j = nodes[j].preNode;
        result[k] = v + 1;
        for (; k >= 0; k--) {
            printf("%d%s", result[k], k == 0 ? " ":"->");
        printf(": %d \n", nodes[i].weight);
弗洛伊德(Floyd)
即：任意两个顶点之间的最短距离，单资源最短路径为其结果子集
因此求两点间最短路径过程和单资源最短路径很相似，这里只需要不停引入一个个顶点，以此为中间节点，类似单资源最短路径，不停的更新其他所有顶点距离即可，更新过程用矩阵的方式储存两点之间的最短路径，并且以矩阵的方式储存preNode即可(当然也可以像单资源最短路径似的，采用新边集数组基础结构保存)，如下图所示
深刻理解了单资源最短路径后，此过程将会非常简单，参考上图，这里实际使用的是索引0、1、2、3、4，没有A、B、C、D、E：实际使用矩阵图如下所示，且preNode路径图，指向自己或者没有路径的都标记为-1，标识都表示没有更短路径，直接取当前索引和即可
参考上面的索引图，下面为实现步骤逻辑：
1.声明preNode二维矩阵paths 和 最短路径权值矩阵lines，系统给定的默认直接路径的邻接矩阵为linesList
2.根据系统给定的邻接矩阵linesList，将对应位置的paths和lines分别赋值，其中preNode则为横向索引，如果顶点到自己或者无路径(权值为0或者∞)，则这里preNode赋值为-1，lines的权值直接从邻接矩阵拷贝过来即可
3.引入顶点m(默认第一个顶点), 从第m个顶点开始执行循环流程
4.通过引入的顶点m，将其作为中间点(最小点)，对顶点i到其他顶点距离进行优化
5.通过顶点i到m点距离与m点到其他顶点距离之和，与顶点直接到其他顶点的距离对比(同单资源一致)，如果距离更短，则更新距离和preNode，否则不更新
6.重复步骤五，切换下一个顶点，即i++, 通过引入的顶点m，对其他顶点进行调整，即返回步骤5，继续向后执行
7.通过引入的顶点m，更新完毕其余节点距离后，接着引入下一个顶点(m+1)，继续调整到其他顶点的距离，重复步骤5
8.引入顶点m已经到达最后一个顶点，直接结束，两点间最小路径已经生成
代码如下：
void showDoubleMinShortPathByFloyd(int start, int end) {
    int paths[N][N]; //用于表示上一个路径的索引，为零则没有优化
    int lines[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            lines[i][j] = linesList[i][j];
            if (i != j && lines[i][j] < MAXINT) {
                paths[i][j] = i; //保存i-j点经过的路径i， 结果则可以表示为i->j
            }else {
                paths[i][j] = -1;
    //通过动态规划来求出每两个点之间的最短路径
    //在每个点中添加一个顶点，查看是否总长小于直接长度，小于则替换，那么替换完成之后则就是最短路径
    for (int k = 0; k < N; k++) {
        //ij表示的是对应顶点坐标，k表示的新加入的索引
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (lines[i][k] + lines[k][j] < lines[i][j]) {
                    lines[i][j] = lines[i][k] + lines[k][j];
                    paths[i][j] = k; //记录优化过的路径(从1开始，-1未优化过)
void printPath(int lines[N][N], int paths[N][N], int start, int end) {
    //那么最短路径的长度则为
    printf("\n弗洛伊德:\n");
    printf("%d->", start + 1);
    int last = start;
    int next = paths[last][end];
    while (next != -1 && next != last) {
        printf("%d-", next + 1);
        last = next;
        next = paths[next][end];
    printf("%d : %d\n", end + 1, lines[start][end]);
    printf("生成的path矩阵:\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", paths[i][j] + 1);
        printf("\n");
    剪刀石头布啊
        ios工程师 @天津