【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊

2017-09-19 本文已影响543人 NotFunGuy

图的最短路径

【对于非网图】没有边上的权值，它的最短路径就是两个顶点之间经过的边数目最少的路径。
【对于网图】最短路径是指两顶点之间经过的边上权值之和和最少的路径，并且称路径上的第一个顶点是源点，最后一个顶点是终点。
非网图可以看做所有边的权值都为1的网图。
求解最短路径的方法有两种：
- 从某个源点到其余各个顶点的最短路径问题：迪杰斯特拉(Dijkstra)算法。
- 图中所有到多有顶点的最短路径问题：弗洛伊德(Floyd)算法

本文所用图

一、迪杰斯特拉(Dijkstra)算法

迪杰斯特拉(Dijkstra)算法核心：按照路径长度递增的次序产生最短路径。

迪杰斯特拉(Dijkstra)算法步骤：（求图中v0到v8的最短路径）并非一下子求出v0到v8的最短路径，而是一步一步求出它们之间顶点的最短路径，过过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得出源点与终点的最短路径。

迪杰斯特拉(Dijkstra)算法代码实现

核心代码

/**
 * Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]
 * P[v]的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和
 */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc * P, ShortPathTable * D){
    
    int v, w, k = 0, min;
    int final[MAXVEX]; // final[w] = 1 表示求得顶点v0到vw的最短路径
    
    for (v = 0; v < G.numVertexes; v++) {  // 初始化数据
        
        final[v] = 0;   // 全部顶点初始化为未知最短路径状态
        (*D)[v] = G.arc[v0][v];  // 将与v0点有连线的顶点加上权值
        (*P)[v] = 0;    // 初始化路径数组P为0
    }
    
    (*D)[v0] = 0; // v0到v0路径为0
    final[v0] = 1; // v0到v0不需要求路径
    
    for (v = 1; v < G.numVertexes; v++) {  // 开始主循环，每次求得v0到某个v顶点的最短路径
        
        min = INFINITY;
        
        for (w = 0; w < G.numVertexes; w++) {  // 寻找离v0最近的顶点
            if (!final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w];   // w顶点离v0顶点更近
            }
        }
        
        final[k] = 1;  // 将目前找到的最近的顶点置为1
        
        for (w = 0; w < G.numVertexes; w++) {  // 修正当前最短路径及距离
            if (!final[w] && (min + G.arc[k][w] < (*D)[w])) {   // 如果经过v顶点的路径比现在这条路径的长度短的话
                                                                // 说明找到了根断的路径
                (*D)[w] = min + G.arc[k][w];  // 修改当前路径长度
                (*P)[w] = k;
            }
        }
    }
}

完整代码和测试

#include <stdio.h>
#include <stdlib.h>

#define MAXEDGE 20
#define MAXVEX 10
#define INFINITY 65535

typedef struct {
    
    int vex[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

typedef int Patharc[MAXVEX];  // 用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX]; // 用于存储到各点最短路径的权值和

/**
 * 创建图
 */
void CreateMGraph(MGraph * G){
    
    int i, j;
    
    G->numVertexes = 9;  // 9个顶点
    G->numEdges = 16;  // 16条边
    
    for (i = 0; i < G->numVertexes; i++) // 初始化图
        G->vex[i] = i;  //给顶点编号 这里是0 到 8
    
    for (i = 0; i < G->numVertexes; i++) {  // 初始化图
        for (j = 0; j < G->numVertexes; j++) {
            if (i == j)
                G->arc[i][j] = 0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITY;
        }
    }
    
    G->arc[0][1] = 1;
    G->arc[0][2] = 5;
    G->arc[1][2] = 3;
    G->arc[1][3] = 7;
    G->arc[1][4] = 5;
    
    G->arc[2][4] = 1;
    G->arc[2][5] = 7;
    
    G->arc[3][4] = 2;
    G->arc[3][6] = 3;
    G->arc[4][5] = 3;
    
    G->arc[4][6] = 6;
    G->arc[4][7] = 9;
    
    G->arc[5][7] = 5;
    
    G->arc[6][7] = 2;
    G->arc[6][8] = 7;
    
    // 利用邻接矩阵的对称性
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j < G->numVertexes; j++)
            G->arc[j][i] = G->arc[i][j];
}

/**
 * Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]
 * P[v]的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和
 */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc * P, ShortPathTable * D){
    
    int v, w, k = 0, min;
    int final[MAXVEX]; // final[w] = 1 表示求得顶点v0到vw的最短路径
    
    for (v = 0; v < G.numVertexes; v++) {  // 初始化数据
        
        final[v] = 0;   // 全部顶点初始化为未知最短路径状态
        (*D)[v] = G.arc[v0][v];  // 将与v0点有连线的顶点加上权值
        (*P)[v] = 0;    // 初始化路径数组P为0
    }
    
    (*D)[v0] = 0; // v0到v0路径为0
    final[v0] = 1; // v0到v0不需要求路径
    
    for (v = 1; v < G.numVertexes; v++) {  // 开始主循环，每次求得v0到某个v顶点的最短路径
        
        min = INFINITY;
        
        for (w = 0; w < G.numVertexes; w++) {  // 寻找离v0最近的顶点
            if (!final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w];   // w顶点离v0顶点更近
            }
        }
        
        final[k] = 1;  // 将目前找到的最近的顶点置为1
        
        for (w = 0; w < G.numVertexes; w++) {  // 修正当前最短路径及距离
            if (!final[w] && (min + G.arc[k][w] < (*D)[w])) {   // 如果经过v顶点的路径比现在这条路径的长度短的话
                                                                // 说明找到了根断的路径
                (*D)[w] = min + G.arc[k][w];  // 修改当前路径长度
                (*P)[w] = k;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    
    int i, j, v0;
    
    MGraph G;
    Patharc P;
    
    ShortPathTable D;
    v0 = 0;  // 求v0到其余各点的最短路径
    
    CreateMGraph(&G);
    
    ShortestPath_Dijkstra(G, v0, &P, &D);
    
    printf("源点到各个顶点的最短路径如下：\n");
    
    for (i = 1; i < G.numVertexes; i++) {
        
        printf("v%d - v%d 最短路径为：%2d 所经过顶点: ",v0, i, D[i]);
        
        j = i;
        
        while (P[j] != 0) {
            printf("v%d ", P[j]);
            j = P[j];
        }
        printf("\n");
    }
    return 0;
}

测试结果

代码解释

用邻接矩阵构建图。
用Patharc数组存储最短路径下标,用ShortPathTable数组存储各点最短路径的权值和。
最终返回的数组D和数组P，是可以得到v0到任意一个顶点的最短路径和路径长度的。
该算法的时间复杂度为O(n^2)（因为有一个for循环嵌套）。

二、弗洛伊德(Floyd)算法

弗洛伊德(Floyd)算法是一个经典的动态规划算法。

弗洛伊德(Floyd)算法思路

从任意节点i到任意节点j的最短路径不外乎2种可能:1是直接从i到j，2是从i经过若干个节点k到j。
所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立;
如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

弗洛伊德(Floyd)算法描述

从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大.
对于每一对顶点u 和 v，看看是否存在一个顶点 w使得从 u 到 w再到 v比己知的路径更短。如果是更新它。

弗洛伊德(Floyd)算法代码实现

弗洛伊德(Floyd)算法核心代码

/**
 * Floyd算法，求网图G中各个顶点v到其余各个顶点w的最短路径P[v][w] 以及带权长度D[v][w]
 */
void ShortestPaht_Floyd(MGraph G, Patharc *P, ShortPathTable *D){
    
    int v,w,k;
    
    for (v = 0; v < G.numVertexes; v++) {  // 初始化D与P
        for (w = 0; w < G.numVertexes; w++) {
            (*D)[v][w] = G.arc[v][w];  //(*D)[v][w] 值即为对应点之间的权值
            (*P)[v][w] = w;
        }
    }
    
    for (k = 0; k < G.numVertexes; k++) {
        for (v = 0; v < G.numVertexes; v++) {
            for (w = 0; w < G.numVertexes; w++) {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {  // 如果经过下标为K顶点路径比原两点间路径更短
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];  // 将当前两点间权值设置为更小的一个
                    (*P)[v][w] = (*P)[v][k];   // 路径设置为经过下标为k的顶点
                }
            }
        }
    }
}

完整代码+测试代码

#include <stdio.h>
#include <stdlib.h>

#define MAXEDGE 20
#define MAXVEX 10
#define INFINITY 65535

typedef struct {
    
    int vex[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

/**
 * 创建图
 */
void CreateMGraph(MGraph * G){
    
    int i, j;
    
    G->numVertexes = 9;  // 9个顶点
    G->numEdges = 16;  // 16条边
    
    for (i = 0; i < G->numVertexes; i++) // 初始化图
        G->vex[i] = i;  //给顶点编号 这里是0 到 8
    
    for (i = 0; i < G->numVertexes; i++) {  // 初始化图
        for (j = 0; j < G->numVertexes; j++) {
            if (i == j)
                G->arc[i][j] = 0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITY;
        }
    }
    
    G->arc[0][1] = 1;
    G->arc[0][2] = 5;
    G->arc[1][2] = 3;
    G->arc[1][3] = 7;
    G->arc[1][4] = 5;
    
    G->arc[2][4] = 1;
    G->arc[2][5] = 7;
    
    G->arc[3][4] = 2;
    G->arc[3][6] = 3;
    G->arc[4][5] = 3;
    
    G->arc[4][6] = 6;
    G->arc[4][7] = 9;
    
    G->arc[5][7] = 5;
    
    G->arc[6][7] = 2;
    G->arc[6][8] = 7;
    
    // 利用邻接矩阵的对称性
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j < G->numVertexes; j++)
            G->arc[j][i] = G->arc[i][j];
}

/**
 * Floyd算法，求网图G中各个顶点v到其余各个顶点w的最短路径P[v][w] 以及带权长度D[v][w]
 */
void ShortestPaht_Floyd(MGraph G, Patharc *P, ShortPathTable *D){
    
    int v,w,k;
    
    for (v = 0; v < G.numVertexes; v++) {  // 初始化D与P
        for (w = 0; w < G.numVertexes; w++) {
            (*D)[v][w] = G.arc[v][w];  //(*D)[v][w] 值即为对应点之间的权值
            (*P)[v][w] = w;
        }
    }
    
    for (k = 0; k < G.numVertexes; k++) {
        for (v = 0; v < G.numVertexes; v++) {
            for (w = 0; w < G.numVertexes; w++) {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {  // 如果经过下标为K顶点路径比原两点间路径更短
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];  // 将当前两点间权值设置为更小的一个
                    (*P)[v][w] = (*P)[v][k];   // 路径设置为经过下标为k的顶点
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {

    int v, w,k;
    
    MGraph G;
    Patharc P;
    ShortPathTable D;
    
    CreateMGraph(&G);
    ShortestPaht_Floyd(G, &P, &D);
    
    printf("各顶点间最短路径如下：\n");
    
    for (v = 0; v < G.numVertexes; v++) {
        for (w = v+1; w < G.numVertexes; w++) {
            printf("v%d - v%d weight：%d", v,w,D[v][w]);
            k = P[v][w];    // 获得第一个路径顶点下标
            printf(" path: %d", v);  // 打印源点
            
            while (k != w) {  // 如果路径顶点下标不是终点
                printf(" —> %d",k);  // 打印路径顶点
                k = P[k][w];   // 获得下一个路径顶点下标
            }
            printf(" -> %d\n", w);
        }
        printf("\n");
    }    
    return 0;
}

弗洛伊德(Floyd)算法

代码解释

弗洛伊德(Floyd)算法的代码非常简洁，就是一个二重初始化加上一个三重循环权值修正，就完成了所有顶点到所有顶点的最短路径计算。
弗洛伊德(Floyd)算法的时间复杂度为O(n^3)。

【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊

图的最短路径

一、迪杰斯特拉(Dijkstra)算法

迪杰斯特拉(Dijkstra)算法代码实现

核心代码

完整代码和测试

代码解释

二、弗洛伊德(Floyd)算法

弗洛伊德(Floyd)算法思路

弗洛伊德(Floyd)算法描述

弗洛伊德(Floyd)算法代码实现

弗洛伊德(Floyd)算法核心代码

完整代码+测试代码

代码解释

猜你喜欢

热点阅读