【数据结构】最短路径算法之迪杰斯特拉算法

深碍√TFBOYSˉ_ 2022-10-02 12:51 190阅读 0赞

## 基本概念 ##

最简单的最短路径是求中转次数最少的路径，而不考虑每条边的权值。而在实际问题中，路径长度的度量就不再是路径上的边数，而是**路径上所有边的权值之和**。

在**有向网**中，习惯上称路径的第一个顶点为**源点（Source）**，最后一个顶点为**终点（Destination）**。

下面主要讨论**两种**最常见的最短路径问题：

一、从**某个源点**到其余顶点的最短路径；

二、求**每一对顶点**之间的最短路径。

**迪杰斯特拉(Dijkstra)算法**用于求解第一种问题，时间复杂度为**O(n²)**；**弗洛伊德(Floyd)算法**用于求解第二种问题，时间复杂度为**O(n³)**。

从实现形式上来说，弗洛伊德算法比迪杰斯特拉算法更为**简洁**。

## 迪杰斯特拉算法（单源点） ##

**<逻辑思路>**

（1）从单源点出发，求到各个顶点的最短路径。该问题类似于就**有向连通网**的**最小生成树**；

（2）因此同样需要**辅助数组**来记录**顶点是否被归并**和**最短路径长度**；

（3）迪杰斯特拉算法的巧妙之处就在于设计了三个辅助数组：

1. **一维数组S\[\]**：记录顶点vi是否被确定最短路径长度，即该顶点是否被归并到**终点集合**中。**初始化**：S\[v0-1\] = TRUE；

2. **一维数组Path\[\]**：记录顶点vi的**直接前驱**。譬如存在最短路径<v1,v4,v3>，v4的直接前驱是v1，v3的直接前驱是v4，这样一来，依靠直接前驱数组就能将路径**连接**起来。**初始化**：若源点v0到vi有弧，则Path\[vi-1\]为v0-1（编号/下标）；否则为-1。

3. **一维数组D\[\]**：记录从源点v0到终点vi的**最短路径长度**。**初始化**：若源点v0到vi有弧，则D\[vi-1\]为弧上的权值；否则为∞。

（4）算法开始时，先找到**D\[\]**上的最小值，然后并入第一个终点v1，并将**S\[v1-1\]**的值设为TRUE；

（5）由于加入了终点v1，相当于v0多了一个**中转点**，所以需要对**D\[\]**上的值进行更新；

（6）更新后继续找**D\[\]**上的最小值，继而找到了顶点v2，因为**S\[v2-1\]**的值为FALSE，即v2未被归并到终点集合，所以可以将它并入；

（7）若到v2的最短路径是<v0,v1,v2>，则将v2的直接前驱改为v1，即**Path\[v2-1\] = v1-1**；

（8）反复执行以上过程（n-1次），直至所有顶点被并入**终点集合**。

**<实现思路>——以邻接矩阵为存储结构的有向网**

（1）对应**<逻辑思路>**步骤(3)的初始化：

1. S\[v0-1\] = TRUE;

2. D\[vi-1\] = G.arcs\[v0-1\]\[vi-1\];

3. if(G.arcs\[v0-1\]\[vi-1\] != MaxInt) Path\[vi-1\] = v0-1; /\*MaxInt表示无穷∞，值为326767\*/

（2）对应**<逻辑思路>**步骤(8)的n-1次循环

1. 步骤(4)：D\[v1\] = Min(D);

2. 步骤(6)：if(S\[v1-1\] = FALSE) S\[v1-1\] = TRUE;

3. 步骤(5)和步骤(7)： if(D\[v1-1\] + G.arcs\[v1-1\]\[v2-1\] < D\[v2-1\]) \{D\[v2-1\] = D\[v1-1\] + G.arcs\[v1-1\]\[v2-1\]; Path\[v2-1\] = v1-1;\}

#define TRUE 1
    #define FALSE 0
    
    void ShortestPath_DIJ(AMGraph G, int v0)
    {
        int S[vexnum];
        int Path[vexnum];
        int D[vexnum];
    
        int i = LocateVex(G, v0);
    
        for(int vi = 1; vi <= G.vexnum; vi++) /*初始化*/
        {
            int j  =LocateVex(G, vi);
    
            S[j] = FALSE;
    
            D[j] = G.arcs[i][j];
    
            if(D[j] < MaxInt) Path[j] = i;    /*小于MaxInt即v0与vi间存在弧*/
            else Path[j] = -1;                /*若vi的直接前驱不是v0，则置为-1*/
        }
        
        S[i] = TRUE;
        D[i] = 0;                             /*源点到源点的路径长度为0*/
    
    /*----------初始化结束-----------*/
    
        for(int t = 1; t < G.vexnum; t++)     /*循环n-1次*/
        {
            int v;                            /*下一个终点*/
    
            for(vi = 1; vi <= G.vexnum; vi++)
            {
                int min = MaxInt;             /*min保存最小值*/
    
                int j = LocateVex(G, vi);
    
                if(S[j] = FALSE && D[j] < min)/*找出最小权值的边*/
                    {v = vi; min = D[j];}
            }
    
            S[v-1] = TRUE;                    /*将v加入终点集合*/
            
            int k = LocateVex(G, v);
            
            for(vi = 1; vi <= G.vexnum; vi++) /*更新最短路径和直接前驱数组*/
            {
                int j = LocateVex(G, vi);
    
                if(S[j] = FALSE && (D[k] + G.arcs[k][j] < D[j])
                {
                    D[j] = D[k] + G.arcs[k][j];
                    Path[j] = k;
                }
            }
        }
    }