適合有向倍訓圖的K-Shortest-Path

https://blog.csdn.net/cysisu/article/details/83411409
以上鏈接的代碼實作的是基于有向圖實作得到k條最短路徑的演算法，k條最短路徑的演算法是在上交大那篇論文中看到的思想，于是在網上找到了這個實作的代碼，但是在利用此代碼接入自己的地圖時規劃出來的路徑有些是不對的，根本不通的，原因就是我們自己的地圖是存在倍訓的，而上述鏈接中的地圖是不存在倍訓的，于是就對其進行了相應的修改：
K-Shortest-Path演算法的思想：
https://www.cnblogs.com/qq952693358/p/7354070.html
改寫這個代碼的程序就是：將其寫成了一個類，在自己的架構中去呼叫，將他的代碼中的函式寫成類中的共有成員函式，在自己的架構中去呼叫介面傳參就可以了，

一.首先講一下如何對演算法進行的修改
主要做了以下幾方面的修改：
（1）在規劃出一條最短路徑后會基于此最短路徑做迭代，迭代的程序中會將逐個將最短路徑中的邊設定為無窮大，然后去更新地圖，此鏈接中給出的代碼是(修改前的代碼)：

vector<vector<float> > K_Shortest_Path::cutEdge(const vector<vector<float> > &NW, vector<DijPath> kSPCost, unsigned int root)
{
    vector<vector<float>>NWCopy = NW;
    for (unsigned int i = 0; i < kSPCost.size(); i++)
    {
        //此for回圈只是為了尋找和root相同的點
        for (unsigned int j = 0; j < kSPCost[i].onePath.size(); j++)
        {
            if (kSPCost[i].onePath[j] == root)
            {
                unsigned int nextVertex = kSPCost[i].onePath[j + 1];
                //1.此處是做出修改的第一步
               if (j >= 1)           
                 {                  
                unsigned int beforeVertex = kSPCost[i].onePath[j - 1];
                  NWCopy[root][beforeVertex] = INF;
               }
                NWCopy[root][nextVertex] = INF;  //設定為不可連接
                break;
            }
        }
    }

    return NWCopy;
}

修改后的代碼：也就是屏蔽掉了if的判斷條件，

vector<vector<float> > K_Shortest_Path::cutEdge(const vector<vector<float> > &NW, vector<DijPath> kSPCost, unsigned int root)
{
    vector<vector<float>>NWCopy = NW;
    for (unsigned int i = 0; i < kSPCost.size(); i++)
    {
        //此for回圈只是為了尋找和root相同的點
        for (unsigned int j = 0; j < kSPCost[i].onePath.size(); j++)
        {
            if (kSPCost[i].onePath[j] == root)
            {
                unsigned int nextVertex = kSPCost[i].onePath[j + 1];
                //1.此處是做出修改的第一步
//                if (j >= 1)
//                {
//                    unsigned int beforeVertex = kSPCost[i].onePath[j - 1];
//                    NWCopy[root][beforeVertex] = INF;
//                }
                NWCopy[root][nextVertex] = INF;  //設定為不可連接
                break;
            }
        }
    }

    return NWCopy;
}

（2）第二處做出的修改：在run()函式中，在基于第一條最短路徑迭代規劃接下來的最短路徑的時候，if的判斷條件進行了修改如下：

//前面的那個節點到終點的一條最短路徑
DijPath secondPath = dij.dijkstra(NWCopy, kSPCost[k - 1].onePath[i], dst);
 if (secondPath.cost > 100000 || secondPath.cost ==0 )//判斷兩點不可以到達
            {
                continue;
            }

之前是：

  DijPath secondPath = dij.dijkstra(NWCopy, kSPCost[k - 1].onePath[i], dst);
 if (secondPath.cost > 100000)//判斷兩點不可以到達
            {
                continue;
            }

cost變數之前是int型別的，在列印secondPath.cost這個值的時候發現有負無窮大的值也有0，所以將cost變數變成unsigned int 型別,這樣就不會出現負無窮大了，另外再將判斷條件加上一個==0，這樣就可以解決了，
以后再換別的地圖去用的時候，這個判斷條件可以根據secondPath.cost的只去修改，
二.其次講一下在這個將此鏈接中的代碼用在自己的框架中時遇到的問題：
(1)系統總是出現崩潰死掉的情況，原因是定義物件指標的時候沒有進行實體化；

vector<vector<unsigned int>> TaskManagerAGV::show_ksp(int startpoint, int endpoint)
{
//    qDebug()<<"entre the show_ksp";
    vector<vector<unsigned int>>pathlist,pathlistShow;

    QVector<QStringList> shortPathMatrix = getshortpathmatrix();
    pathlist = k_short_path->searchPath(startpoint, endpoint, shortPathMatrix, pathNodeMap, NodeHotValue);
    return pathlist;
}

k_short_path在類中的定義如下：

K_Shortest_Path *k_short_path;

只是做了如上定義，沒有進行實體化：

k_short_path = new K_Shortest_Path();

在類 K_Shortest_Path中的建構式中加上此實體化的代碼，系統每次運行的時候就不會崩潰了，