深入解析最短路径算法

int ShortPath(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)  
{  
    //用戴克斯特拉算法求有向图G中v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]。  
    //若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。  
    //final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。  
      
    for(v = 0;v < G.vexmun;v++)  
    {  
        final[v] = FALSE;  
        D[v] = G.WeiArcs[v0][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集合  
      
    //开始主循环，每次求得v0到某个顶点v的最短路径，并将v加到S集合中  
    for(i = 1; i < G.vexnum; i++)    //其余G.vexnum - 1个顶点  
    {  
        min = INFINITY; //当前所知离v0点的最近距离  
        for(w = 0;w < G.vexnum; i++)  
        {  
            if(!final[w])   //w顶点在V - S中  
            {  
                if(D[w] < min)   //w顶点离v0更近  
                {  
                    v = w;  
                    min = D[w];  
                }  
            }  
        }  
        final[v] = TRUE;    //离v0顶点最近的v加入到S中  
          
        for(w = 0;w < G.vexnum;w++)  //更新当前最算路径及距离  
        {  
            if(!final[w] && (min + G.WeiArcs < D[w]))  
            {  
                D[w] = min + G.WeiArcs[v][w];  
                //p[w] = P[v] + P[w];  
                P[w] = P[v];  
                P[w][w] = TRUE;  
            }  
        }  
    }  
    return 0;  
}  

ok，Dijkstra algorithm介绍完了。

第三节 弗洛伊德算法（Floyd algorithm）


       该算法解决的是有向带权图中两顶点之间最短路径的问题。

弗洛伊德算法的设计过程如下：


       用带权的矩阵WeiArcs来表示带权有向图，如果图中的两个顶点vi和vj是连通的，则用WeiArcs[i][j]表示这两个顶点所形成边的权值；如果vi和vj不连通，即<vi,vj>这条边不存在，那么将WeiArcs[i][j]置为∞。
       要求：求节点vi到节点vj的最短路径。
       设D(i,j,k)为从节点vi到节点vj的以vk（vk∈(0,1,…k)）节点为中间节点的最短路径的长度。例如：从vi到vj这条路径上经过节点vm和节点vk，那么可表示为：vi–>vm–>vk–>vj。

那么，就有：1.若最短路径经过节点vk，则D(i,j,k) = D(i,k,k-1) + D(k,j,k-1)；
                      2.若最短路径不经过节点vk，则D(i,j,k) = D(i,j,k-1)。


所以，求的vi到vj的最短路径可表示为：

老办法，图示的过程如下：

求解的过程见下图：

上述过程描述的弗洛伊德算法的代码如下：

int ShortPath(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)  
{  
    //用Floyd算法求有向图中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w]。  
    //若p[v][w][u]为TRUE,则u是从v到w当前求得的最短路径上的顶点  
    for(v = 0;v < G.vexnum;v++)  
        for(w = 0;w < G.vexnum;w++)  
        {  
            D[v][w] = G.arcs[v][w];  
            if(D[v][w] < INFINITY)   //从v到w有直接路径  
            {  
                P[v][w][u] = TRUE;  
                P[v][w][w] = TRUE;  
            }  
        }  
          
    for(u = 0;u < G.vexnum;u++)  
        for(v = 0;v < G.vexnum;v++)  
            for(w = 0;w < G.vexnum;w++)  
            {  
                if(D[v][u] + D[u][w] < D[v][w])  //从v经u到w的一条更短路径  
                    D[v][w] = D[v][u] < D[u][w];  
                for(i = 0;i < G.vexnum;i++)  
                    P[v][w][i] = P[v][u][i] || P[u][w][i];  
            }  
    return 0;  
}  

第四节 A*搜索算法


       A*搜索算法，俗称A星算法。这是一种在图平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。

       A*算法最核心的部分，就在于它的一个估值函数的设计上：f(n)=g(n)+h(n)。其中，g(n)表示从起始点到任一点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离，f(n)是每个可能试探点的估值。这个估值函数遵循以下特性：


       •如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法；
       •如果h(n)<=“n到目标的实际距离”，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。

       我们可以这样来描述：从出发点(StartPoint,缩写成sp)到终点(EndPoint，缩写成ep)的最短距离是一定的，于是我们可以写一个估值函数来估计出发点到终点的最短距离。如果程序尝试着从出发点沿着某条线路移动到了路径上的另一个点（Otherpoint,缩写成op），那么我们认为这个方案所得到的从sp到ep间的估计距离为：从sp到op实际已走的距离加上估计函数估出的从op到ep的距离。如此，无论我们的程序搜索展开到哪一步，都会得到一个估计值，每一次决策后，将评估值和等待处理的方案一起排序，然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步, 一直循环直到对象移动到目的地，或所有方案都尝试过，却没有找到一条通向目的地的路径则结束。



A*搜索算法的图解过程请看：http://blog.vckbase.com/panic/archive/2005/03/20/3778.html

第五节 相关说明


参考资料：数据结构(严蔚敏)、维基百科之A*搜索算法

第六节 结束语


      想想，写写，画画……