最短路

淡淡的烟草味﹌ 2022-03-18 12:35 252阅读 0赞

最短路

典型用途：交通网络的问题——从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？  
  
交通网络用有向网来表示：顶点——表示城市，弧——表示两个城市有路连通，弧上的权值——表示两城市之间的距离、交通费或途中所花费的时间等。  
如何能够使一个城市到另一个城市的运输时间最短或运费最省？这就是一个求两座城市间的最短路径问题。  
问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n - 1条边。  
常见最短路径问题：单源点最短路径、所有顶点间的最短路径  
（1）如何求得单源点最短路径？  
穷举法：将源点到终点的所有路径都列出来，然后在其中选最短的一条。但是，当路径特别多时，特别麻烦；没有规律可循。  
迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生各顶点的最短路径。  
路径长度最短的最短路径的特点：  
在此路径上，必定只含一条弧 <v\_0, v\_1>，且其权值最小。由此，只要在所有从源点出发的弧中查找权值最小者。  
下一条路径长度次短的最短路径的特点：  
①、直接从源点到v\_2<v\_0, v\_2>（只含一条弧）；  
②、从源点经过顶点v\_1，再到达v\_2<v\_0, v\_1>,<v\_1, v\_2>（由两条弧组成）  
再下一条路径长度次短的最短路径的特点：  
有以下四种情况：  
①、直接从源点到v\_3<v\_0, v\_3>（由一条弧组成）；  
②、从源点经过顶点v\_1，再到达v\_3<v\_0, v\_1>,<v\_1, v\_3>（由两条弧组成）；  
③、从源点经过顶点v\_2，再到达v\_3<v\_0, v\_2>,<v\_2, v\_3>（由两条弧组成）；  
④、从源点经过顶点v\_1 ,v\_2，再到达v\_3<v\_0, v\_1>,<v\_1, v\_2>,<v\_2, v\_3>（由三条弧组成）；  
其余最短路径的特点:  
①、直接从源点到v\_i<v\_0, v\_i>（只含一条弧）；  
②、从源点经过已求得的最短路径上的顶点，再到达v\_i（含有多条弧）。  
Dijkstra算法步骤：  
初始时令S=\{v\_0\}, T=\{其余顶点\}。T中顶点对应的距离值用辅助数组D存放。  
D\[i\]初值：若<v\_0, v\_i>存在，则为其权值；否则为∞。  
从T中选取一个其距离值最小的顶点v\_j，加入S。对T中顶点的距离值进行修改：若加进v\_j作中间顶点，从v\_0到v\_i的距离值比不加 vj 的路径要短，则修改此距离值。  
重复上述步骤，直到 S = V 为止。

算法实现：

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
    { // 用Dijkstra算法求有向网 G 的 v0 顶点到其余顶点v的最短路径P[v]及带权长度D[v]。
        // 若P[v][w]为TRUE,则 w 是从 v0 到 v 当前求得最短路径上的顶点。  P是存放最短路径的矩阵，经过顶点变成TRUE
        // final[v]为TRUE当且仅当 v∈S,即已经求得从v0到v的最短路径。
        int v,w,i,j,min;
        Status final[MAX_VERTEX_NUM];
        for(v = 0 ;v < G.vexnum ;++v)
        {
            final[v] = FALSE;
            D[v] = G.arcs[v0][v].adj;        //将顶点数组中下标对应是 v0 和 v的距离给了D[v]
            for(w = 0;w < G.vexnum; ++w)
                P[v][w] = FALSE;            //设空路径
            if(D[v] < INFINITY)
            {
                P[v][v0] = TRUE;
                P[v][v] = TRUE;
            }
        }
        D[v0]=0;
        final[v0]= TRUE; /* 初始化,v0顶点属于S集 */
        for(i = 1;i < G.vexnum; ++i) /* 其余G.vexnum-1个顶点 */
        { /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
            min = INFINITY; /* 当前所知离v0顶点的最近距离 */
            for(w = 0;w < G.vexnum; ++w)
                if(!final[w]) /* w顶点在V-S中 */
                    if(D[w] < min)
                    {
                        v = w;
                        min = D[w];
                    } /* w顶点离v0顶点更近 */
                    final[v] = TRUE; /* 离v0顶点最近的v加入S集 */
                    for(w = 0;w < G.vexnum; ++w) /* 更新当前最短路径及距离 */
                    {
                        if(!final[w] && min < INFINITY && G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w]))
                        { /* 修改D[w]和P[w],w∈V-S */
                            D[w] = min + G.arcs[v][w].adj;
                            for(j = 0;j < G.vexnum;++j)
                                P[w][j] = P[v][j];
                            P[w][w] = TRUE;
                        }
                    }
        }
    }