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; }

运行结果