Dijkstra算法与Floyed算法

前一章我们讲了图的最小生成树的算法，今天我们来讲一讲最短路径的算法——Dijkstra算法与Floyed算法。

Dijkstra算法

Dijkstra算法，目的是求的图中的一点，到其余顶点的最短路径；Floyed算法，目的是求图中任意两个顶点之间的最短路径。其实从Dijkstra算法去实现Floyed算法很简单，再多做一次循环去计算每个顶点到除了它自己的其他点的最短路径即可，之所以会有Floyed算法，是由于Floyed算法的简洁优美（Floyed算法的思想是利用了动态规划的思想）。现在，我们具体来介绍下这两个算法吧！

（该图为Dijkstra算法与Floyed算法的使用图，有向图或无向图对算法的改动其实很小）

首先，我们来介绍下Dijkstra（迪杰斯特莱算法）。该算法是从其中一个顶点出发，通过广度优先遍历搜索，实现最短路径的计算。现在，假设我们从A这个点出发，开始做广度优先遍历，发现有两个点A是可以到达的，就是C和G点，我们观察到A->C的代价是5，A-> G的代价是7，所以，首先得出A->C和A->G的最短路径是5、7；随后我们从C点开始广度优先遍历搜索（也可能从G点继续开始广度优先遍历搜索），发现C点可以到达的点有G、F、D三个点，在加上出发点，我们发现了三条路径：A->C->G、A->C->F、A->C->D，由于前一步我们得出A->C的最短路径代价为5，所以我们只需要计算C->G、C->F、C->D的最短路径代价，观察得出分别为17、3、1；所以得出A->C->G、A->C->F、A->C->D的最短路径代价为17+5，3+5，1+5，但是，这真的是真的最短路径代价吗？我们从第一步得出A->G的最短路径代价为7，显然A->C->G的这条最短路径代价大于我直接从A->G这条路径，所以，在更新时，A->G的最短路径代价依旧保留为A->G的最短路径代价；如果说我的A->C->G的最短路径代价比我A->G的最短路径代价还小，更新时A->G的最短路径代价就更新为从A->C->G的最短路径代价的值。因此，我们可以总结出Dijkstra算法的一个最短路径计算选择公式：

dw = min{dw, dv + Cv, w}

通过Dijkstra算法计算过后，我们得出从A顶点到其余顶点的最短路径值图（每个顶点旁边的数值为最短路径的代价值）

红色的线就是最短路径的选择，现在我们贴上代码（代码正确性未检验，我是根据伪代码自己完成的，但是提供了思路，并且我没有实现路径的记录，只是实现了最短路径代价值的记录）

/**
 * 迪杰斯特莱算法，求某一点到其余所有顶点的最短路径问题
 * @param G
 */
void Dijkstra(ALGraph G) {
    VertexType v, start;
    cout << "请输入一个开始的顶点" << endl;
    cin >> start;
    G.vertices[LocateVex(G, start)].dist = 0;
    int knows = G.vexnum;
    while (knows --) {
        int loc = FindMinDist(G);
        G.vertices[loc].know = true;
        ArcNode *p = G.vertices[loc].firstarc;
        while (p != NULL) {
            if (!G.vertices[p -> adjvex].know) {
                if (G.vertices[loc].dist + *(p -> info) < G.vertices[p -> adjvex].dist) {
                    G.vertices[p -> adjvex].dist = G.vertices[loc].dist + *(p -> info);
                }
            }
            p = p -> nextarc;
        }
    }
}

ALGraph图的结构我是采用了邻接表来实现，如果采用邻接矩阵，那就是去遍历矩阵中的每一个值。

附上ALGraph的结构实现：

#define MAX_NAME 3
#define INFINITY 2e10

typedef int InfoType;
typedef char VertexType[MAX_NAME];

#define MAX_VERTEX_NUM 20
using namespace std;

enum GraphKind{DG, DN, UDG, UDN};

//弧（边）的结构信息
struct ArcNode {
    int adjvex;
    ArcNode *nextarc;
    InfoType *info;
};

//图的节点信息
typedef struct {
    int degree;
    int dist;
    bool know;
    VertexType data;
    ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

//图的整体信息
struct ALGraph {
    AdjList vertices;
    int vexnum, arcnum;
    int kind;
};

Floyed算法

接着，我们在说说Floyed算法（弗洛伊德算法），目前我只是实现了在邻接矩阵的图结构为基础的Floyed算法，邻接矩阵的还在思考当中。

Floyed算法有一个很重要的思想，就是动态规划，由于我们Floyed算法相比与Dijkstra算法，计算量更大，要考虑方方面面，需要计算任意两个顶点之间的最短路径，因此，采用动态规划的实现，可以大大提高计算速度，减少计算量，其本质计算公式和Dijkstra算法计算公式一样：

D[v][w] = min{D[v][w], D[v][k] + D[k][w]}

相比与Dijkstra算法的双重循环，最基本的Floyed算法需要三重循环，一层是两个顶点之间的中间连接点循环，两层路径端点的循环，通过最外层的循环来实现两个顶点之间的连接点，内两层循环实现路径两端端点的变动实现。

弗洛伊德代码实现如下：

/**
 * 将图的邻接表转换为邻接矩阵的形式
 * @param
 * G        图的邻接表数据结构 
 * @param 
 * P        路径二位数组 
 * @param 
 * D        最短路径的权值 
 */
void Link2Martir(ALGraph G, int *graph) {

}

/**
 * 弗洛伊德算法
 * @param G
 */
void Floyed(ALGraph G) {
    int P[G.vexnum][G.vexnum], D[G.vexnum][G.vexnum], graph[G.vexnum][G.vexnum];
    for (int i = 0; i < G.vexnum; ++ i) {
        for (int j = 0; j < G.vexnum; ++ j) {
            D[i][j] = graph[i][j];
            P[i][j] = j;
        }
    }
    for (int i = 0; i < G.vexnum; ++i) {
        for (int j = 0; j < G.vexnum; ++j) {
            for (int k = 0; k < G.vexnum; ++k) {
                D[j][k] = D[j][k] > D[j][i] + D[i][k] ? D[j][i] + D[i][k] : D[j][k];
                P[j][k] = k;
            }
        }
    }
}

由于我是将邻接表转换成了邻接矩阵的形式，所以在函数Floyed（ALGraph G）中，graph[][]这个int类型的数组就是转换后的邻接矩阵，然后我们设置一个P[][]的二维数组进行记录从X->Y的前驱顶点的位置，上面的图转换后P[][]数组的形式如下：

（附上一个视频，这里的Floyed算法我个人觉得还行，我是通过这个来在重新理解的）

https://www.youtube.com/watch?v=1ndAomKMZ24