Floyd算法实现每一对顶点之间的最短路径

之前介绍了Dijkstra算法求某个顶点到其他每个顶点之间的最短路径，那么求每一对顶点的最短路径呢？对，可以重复调用Dijkstra算法，Dijkstra算法的时间复杂度是O(n*n),调用n次，所以总的时间复杂度是O(n*n*n)，接下来介绍Floyd算法，时间复杂度也是O(n*n*n)

下面是书上介绍的

怎么理解呢？无非就是对每一对顶点，循环n次(n为图的顶点个数)，每次比较(比如当前顶点编号为i,j)原来路径长度是否大于加入顶点k后的路径长度(i-j路径长度和i-k-j路径长度)，如果是，就更新i-j之间的路径及长度，最终得到的就是每对顶点之间的最短路径
比如这个图

初始状态下:

顶点          最短路径长度          最短路径        
A-B          2                  A-B
A-C          无穷大              A-C
A-D          11                 A-D
B-C          9                  B-C
B-D          5                  B-D
C-D          1                  C-D 

Floyd算法:

void adjaMultiList::floyd()
{
    //path保存所有顶点到其他顶点的最短路径，比如顶点a,b,c,d，a-b的最短路径是a-d-b,而b-a
    //的最短路径是b-d-a，所以路径还是不同的
    vector<int> *path = new vector<int>[iVertex*iVertex];
    int iCount = 0;
    for (int i = 0; i < iVertex; ++i)
        for (int j = 0; j < iVertex; ++j)
        {
            if (i != j)//比如顶点a到顶点a的最短路径没意义
            {
                path[iCount].push_back(i);//初始时a,b间最短路径即为a-b
                path[iCount].push_back(j);
            }

            iCount++;
        }


    ////1====================================================================
    ////测试用，查看vector数组：
    //cout << endl << endl;
    //for (int i = 0; i < iVertex; ++i)
    //  for (int j = i + 1; j < iVertex; ++j)
    //  {

    //      for (vector<int>::iterator it = path[i*4+j].begin(); it != path[i*4+j].end(); ++it)
    //          cout << vertexElem[*it].data << "-";
    //      cout << "\b " << endl;
    //  }
    //cout << endl << endl;




    //动态创建二维数组
    int **pi = new int*[iVertex];
    for (int i = 0; i < iVertex; ++i)
    {
        pi[i] = new int[iVertex];
    }

    //初始化数组
    for (int i = 0; i < iVertex; ++i)
        for (int j = 0; j < iVertex; ++j)
            pi[i][j]=pi[j][i] = getWeight(i, j);

    for (int k = 0; k < iVertex; ++k)
        for (int i = 0; i < iVertex; ++i)
            for (int j = i + 1; j < iVertex; ++j)//顶点i-j路径和j-i路径相反，没必要让
                //j从0开始
                if (pi[i][k] + pi[k][j] < pi[i][j])
                {
                    pi[j][i] = pi[i][j] = pi[i][k] + pi[k][j];

                    int index = i * 4 + j;
                    int index1 = i * 4 + k;
                    int index2 = k * 4 + j;
                    //修改路径，将i-j的路径修改为i-k的加上k-j的，不过要删除重复的一个元素
                    //比如原来i=4,j=6,k=2
                    //   i-j:4-5-6
                    //   i-k:4-7-2
                    //   k-j:2-1-6

                    //1: 首先将i-j修改为删除i-k路径的最后一个元素的vector，
                    //   i-j为4-7

                    //2: 然后加上k-j路径中的元素
                    //   i-j:4-7-2-1-6
                    //记住，不要忘了修改j-i的路径


                    //1：
                    path[index]=path[index1];
                    path[index].erase(path[index].end() - 1);

                    //在该vector的end()前插入元素
                    path[index].insert(path[index].end(), path[index2].begin(), path[index2].end());
                    path[i + j * 4].erase(path[i + j * 4].begin(), path[i + j * 4].end());
                    path[i + j * 4].insert(path[i+j*4].end(),path[index].rbegin(), path[index].rend());



                    ////1====================================================================
                    ////测试用，查看vector数组：
                    //cout << endl << endl;
                    //for (int i = 0, iCount1 = 0; i < iVertex; ++i)
                    //  for (int j = i + 1; j < iVertex; ++j)
                    //  {

                    //      for (vector<int>::iterator it = path[iCount1].begin(); it != path[iCount1].end(); ++it)
                    //          cout << vertexElem[*it].data << "-";
                    //      cout << "\b " << endl;
                    //      ++iCount1;
                    //  }
                    //cout << endl << endl;


                }

    //输出结果
    cout << "顶点:\t" << "最短路径长度:\t" << "最短路径:" << endl;
    for (int i = 0; i < iVertex; ++i)
        for (int j = i + 1; j < iVertex; ++j)
        {
            cout << vertexElem[i].data << "-" << vertexElem[j].data
                << "\t" << pi[i][j]<<"\t\t";
            for (vector<int>::iterator it = path[i*4+j].begin(); it != path[i*4+j].end();++it)
                cout << vertexElem[*it].data << "-";
            cout << "\b " << endl<<endl;

        }

    //for (int i = 0; i < iVertex; ++i)
    //{
    //  for (int j = 0; j < iVertex; ++j)
    //      cout << pi[i][j] << "\t\t";
    //  cout<< endl;
    //}

    //不要忘了释放内存
    delete []path;
    for (int i = 0; i < iVertex; ++i)
    {
        int *p = pi[i];
        delete[]p;
    }
    delete[]pi;
}

运行结果