N-最短路径中文词语粗分算法研究-2

在上篇文章中，我们已经了解了1-最短路径的计算方式，接下来，我们来看看N-最短路径的求法。

N-最短路径的原理与1-最短路径的相同，只不过求解过程要稍微复杂一点。让我们仍然以上篇文章中的实例来看看如何求解N-最短路径。

一、数据表示

我们沿用上篇文章中的例子，各权重已经标出：

（图一）

根据有向图可以建立如下所示的二维表：

（图二）

二、求PreNode

仍然像1-最短路径一样，求出各个节点的PreNode链表，这里我们以2-最短路径为例：

分别计算源点到各个节点的所有最短路径和次最短路径，我们可以得到如下所示的PreNode链表：

（图三）

说明：在上图中，可以看到源点（0号节点）到A，B，C的路径长度分别只有一条，但是到D的路径长度有两个，一个是3，一个是4，此时在“最短路”处（index＝0）记录长度为3时的PreNode，在“次短路”处（index＝1）处记录长度为4时的PreNode，依此类推。

值得注意的是，此时用来记录PreNode的坐标已经由前文求“1-最短路径”时的一个数（ParentNode值)变为2个数（ParentNode值以及index值）。

如图三所示，到达6号“末”结点的次短路径由两个ParentNode，一个是index=0中的4号结点，一个是index=1的5号结点，它们都使得总路径长度为6。

三、求N-最短路径

求解N-最短路径的方法与1-最短路径是一样的，也是借助堆栈完成的。只不过根据index取值的不同，分多次出栈和入栈。

根据求解方法，我们求得了2-最短路径，路径长度有两种，分别长度为5和6，而路径总共有6条，如下：

最短路径：

• 0, 1, 3, 6,
• 0, 1, 2, 3, 6,
• 0, 1, 2, 4, 5, 6,

次短路径

• 0, 1, 2, 4, 6,
• 0, 1, 3, 4, 5, 6,
• 0, 1, 2, 3, 4, 5, 6,

四、算法实现

实现算法如下：

int CNShortPath::ShortPath()
{
    unsigned int nCurNode=1,nPreNode,i,nIndex;
    ELEMENT_TYPE eWeight;
    PARRAY_CHAIN pEdgeList;

    //    循环从1开始，即从第二个节点开始。遍历所有节点。
    for(;nCurNode<m_nVertex;nCurNode++)
    {
       CQueue queWork;
       //    有CNShortPath调用的上下文可知，入口的m_apCost为列优先排序的CDynamicArray。
       //    换句话说就是：
       //    list<Edge-> m_apCost;
       //    list.sort(m_apCost, less_column_first());
       //    下面这行代码是将该列的边的起始链表元素赋予pEdgeList，以方便遍历。
       //    算法上的含义是取得图上终点为nCurNode的所有边，并将第一条边放入pEdgeList进行对所有边的遍历。
                eWeight=m_apCost-->GetElement(-1,nCurNode,0,&pEdgeList);//Get all the
edges                while(pEdgeList!=0 && pEdgeList-->col==nCurNode)                {
                while(pEdgeList!=0 && pEdgeList-->col==nCurNode)
                
            //    nPreNode是当前边的起点
           nPreNode=pEdgeList-->row;
           //    eWeight是当前边的长度
           eWeight=pEdgeList-->value;//Get the value of edges
                   //   对于dijkstra算法来说，我们需要知道当前节点（终点）的通过不同的前方的点到原点的距离
                   //   并且从中知道最短的路径，然后我们会更新当前节点的父节点和当前节点到原点的距离。
                   //   在这个修改后的多最短路径算法中，我们将（当前节点的父节点，当前节点通过该父节点到原点的距离）视为一个配对
                   //   我们保留一个为m_nValueKind大小的数组，记录这些可能的配对，而不仅仅是保留最小的。
                   //   下面这个循环就是将所有可能的组合放到优先级队列中，然后将来可以从优先级队列中选取前m_nValueKind。
                   //   这里循环范围限定到m_nValueKind主要是考虑以后所需要的不会超过这么多个值。
                   //   这里放入优先级队列的是前向节点和长度，相当于是路径，而不是长度的值的列表，与后面表达的意思不同。
           for(i=0;i<m_nValueKind;i++)
           {
                //    如果起点->0，即判断起点是不是第一个节点。
               if(nPreNode->0)//Push the weight and the pre node
infomation
               {
                    //    起点不是第一个节点。
                    //    判断起点到原点的总长度在索引值为i的时候是不是无穷大。
                                        //      如果无穷大了，就说明前一个点已经无法到达了，说明没有更多到前面节点的路径了
                    //    也不必继续向优先级队列中放入点了。
                   if(m_pWeight[nPreNode-1][i]==INFINITE_VALUE)
                       break;
                    //    将起点，索引值i，和终点到原点的总长度压入优先级队列。
                   queWork.Push(nPreNode,i,eWeight
+m_pWeight[nPreNode-1][i]);
               }
               else
               {
                    //    起点为第一个节点。
                    //    将起点，索引值i，和当前边的长度压入优先级队列
                   queWork.Push(nPreNode,i,eWeight);
                   break;
               }
           }//end for

           //    换到下一条边。
           pEdgeList=pEdgeList-->next;

                }//end while

       //Now get the result queue which sort as weight.
       //Set the current node information
        //    将起点到原点的长度，对于每个索引值都初始化为无穷。
       for(i=0;i<m_nValueKind;i++)
       {
            m_pWeight[nCurNode-1][i]=INFINITE_VALUE;
       }
       //memset((void *),(int),sizeof(ELEMENT_TYPE)*);
       //init the weight
       i=0;
       //       进行循环，索引值小于想要的索引值时，并且优先级队列不为空。
           //   在这里面的i表达的是长度的值的索引，并不代表不同的路径，同一个i可能对应多个路径。
           //   这个循环过后，m_pWeight[nCurNode-1][] 为可能存在的前m_nValueKind个长度值。
           //   并且把前m_nValueKind个路径压入m_nParent对应的队列中。
           //
       while(i<m_nValueKind&&queWork.Pop(&nPreNode,&nIndex,&eWeight)!
=-1)
       {//Set the current node weight and parent
                        //      从以长度为优先级的队列中，提取第一个（最短的）记录。
                        //      将该记录的起点给nPreNode，索引给nIndex，长度给eWeight

            //    如果起点到原点的长度为无穷。（这在第一次循环的时候显然是无穷）
            //    就将这个长度设为最短边的长度。
           if(m_pWeight[nCurNode-1][i]==INFINITE_VALUE)
               m_pWeight[nCurNode-1][i]=eWeight;
           else if(m_pWeight[nCurNode-1][i]<eWeight)//Next queue
           {
                //    否则，如果起点到原点的长度小于当前边的长度
                //    递增索引值，换到下一套选择值去。如果到达了最大索引值就退出循环。
               i++;//Go next queue and record next weight
               //       既然这里有是否会大于最大索引值的判断，何必在while条件里面加那个条件呢？
               if(i==m_nValueKind)//Get the last position
                   break;
                //    将起点到原点的长度，下一个索引值(i+1)，设为队列中元素的长度。
               m_pWeight[nCurNode-1][i]=eWeight;
           }else{
                           //   如果起点到原点的长度 == 队列中的长度， 那么只向当前节点，当前索引的父节点中插入一个配对。
                           //

                           //   如果起点到原点的长度 -> 队列中的长度？
                           //   这是不可能出现的，因为这个数值在队列中是有序的。从小到大。
                           //   因此这个数值的变化规律是初始位无穷大，第一次赋值为最小值，然后逐渐增大。
                   }
           //    将（起点，索引值）压入起点的父节点的队列中去
           m_pParent[nCurNode-1][i].Push(nPreNode,nIndex);
       }
    }//end for

    return 1;
}

//bBest=true: only get one best result and ignore others
//Added in 2002-1-24
void CNShortPath::GetPaths(unsigned int nNode,unsigned int nIndex,int
**nResult,bool bBest)
{
    CQueue queResult;
        //      当前节点为最后一个节点
        unsigned int nCurNode = nNode, nCurIndex = nIndex;
        unsigned int nParentNode,nParentIndex;
        unsigned int nResultIndex = 0;

        if(m_nResultCount ->= MAX_SEGMENT_NUM)        //      Only need 10 result
        {
                return;
        }
        //      将路径第一点设为-1。
        nResult[m_nResultCount][nResultIndex] = -1;     //      Init the result
        //      此时没有设置weight，此时的CQueue的成为了一个Stack。
        queResult.Push(nCurNode, nCurIndex);
    bool bFirstGet;
    while(!queResult.IsEmpty())
        {
                //      从最后的节点循环到第一个节点
                //      这个循环在第一次循环的时候，会把最优解压入结果栈
                //      第二次循环会把分支解压入结果栈。
                while(nCurNode->0)    //
                {
                        //Get its parent and store them in nParentNode,nParentIndex
                        //      取（当前节点，当前索引）的父节点列表的第一个父节点信息。
                        if(m_pParent[nCurNode-1][nCurIndex].Pop(&nParentNode,&nParentIndex,
0,false,true)!=-1)
                        {
                                //      将当前节点变为父节点
                           nCurNode=nParentNode;
                           nCurIndex=nParentIndex;
                        }
                        //      如果当前节点不是第一个节点的话，就将当前节点入栈。
                        if(nCurNode->0)
                queResult.Push(nCurNode,nCurIndex);
                }
                //      如果nCurNode == 0说明取得了合法的结果，而不是异常退出上一个循环。
                if(nCurNode==0)
                {
                        //Get a path and output
                        //      将路径第一点设为起点
                        nResult[m_nResultCount][nResultIndex++]=nCurNode;//Get the first
node
                        //      第一次从queResult取数据的时候，得将这个标志位设为true。
                        //      这样才可以在bModify = false的时候，取得堆栈的头。
                        //      其目的就是要从头遍历堆栈，但是不修改堆栈内部数据，以方便以后遍历用。（循环不就行了？）
                        bFirstGet=true;
                        nParentNode=nCurNode;
                        //      将堆栈遍历，保存结果路径。
                        while(queResult.Pop(&nCurNode,&nCurIndex,0,false,bFirstGet)!=-1)
                        {
                                nResult[m_nResultCount][nResultIndex++]=nCurNode;
                                bFirstGet=false;
                                nParentNode=nCurNode;
                        }
                        //      设置结果位为-1
                        nResult[m_nResultCount][nResultIndex]=-1;//Set the end
                        m_nResultCount+=1;//The number of result add by 1
                        if(m_nResultCount->=MAX_SEGMENT_NUM)//Only need 10 result
                                return ;
                        nResultIndex=0;
                        nResult[m_nResultCount][nResultIndex]=-1;//Init the result

                        if(bBest)//Return the best result, ignore others
                                return ;
                }

                queResult.Pop(&nCurNode,&nCurIndex,0,false,true);//Read the top node
                //      寻找存在多个父节点的节点。
        while(queResult.IsEmpty()==false&&(m_pParent[nCurNode-1]
[nCurIndex].IsSingle()||m_pParent[nCurNode-1]
[nCurIndex].IsEmpty(true)))
                {
               queResult.Pop(&nCurNode,&nCurIndex,0);//Get rid of it
                   queResult.Pop(&nCurNode,&nCurIndex,0,false,true);//Read the top
node
                }
        if(queResult.IsEmpty()==false&&m_pParent[nCurNode-1]
[nCurIndex].IsEmpty(true)==false)
                {
                        //      如果定位到了节点。将下一种选择入栈。
                        m_pParent[nCurNode-1][nCurIndex].Pop(&nParentNode,&nParentIndex,
0,false,false);
                        nCurNode=nParentNode;
                        nCurIndex=nParentIndex;
                        if(nCurNode->0)
                           queResult.Push(nCurNode,nCurIndex);
                }
        }
}

int CNShortPath::Output(int **nResult,bool bBest,int *npCount)
{
        //      sResult is a string array
        unsigned int i;
        m_nResultCount=0;//The
        //      如果节点数只有2个，就没必要那么复杂运算了。直接返回唯一的路径。
        if(m_nVertex<2)
        {
                nResult[0][0]=0;
                nResult[0][1]=1;
                *npCount=1;
                return 1;
        }
        //              对最后一个节点，遍历每一个可能的长度值，将计算所得的路径放入nResult。
        for(i=0;i<m_nValueKind&&m_pWeight[m_nVertex-2][i]<INFINITE_VALUE;i++)
        {
          GetPaths(m_nVertex-1,i,nResult,bBest);
          *npCount=m_nResultCount;
                //      有返回值，并且只想要一个结果
          if(nResult[i][0]!=-1&&bBest)//Get the best answer
                  return 1;
                //      不能超过内部的最大结果数。这个限制条件可以通过动态的vector<T->来消除掉。
      if(m_nResultCount->=MAX_SEGMENT_NUM)//Only need 10 result
                  return 1;
        }
        return 1;
}

说明：m_nValueKind即为N-最短路径中N的取值，在这即N=2.。