Floyd算法实现每一对顶点之间的最短路径_floyd算法求有向图每对顶点最短路径和长度

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

下面是书上介绍的
1
2
3

怎么理解呢？无非就是对每一对顶点，循环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 
1
2
3
4
5
6
7

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

运行结果