算法的思想：
遍历每个结点。然后以这个结点为中间结点来更新所有的结点。
edge(I,j) = min( edge( I , k ) + edge( k , j ) , edge( I , j ) )
edge就是边的长度
例如：
image.png
首先 以 1 为中间结点，更新（1，2），（1，3）（1，4）（1，5）（1，6）（2，3）（2，4）……等所有结点
其次，在以2为中间结点，更新（1，2），（1，3）（1，4）（1，5）（1，6）（2，3）（2，4）……等所有结点
再者，在以3为中间结点，更新（1，2），（1，3）（1，4）（1，5）（1，6）（2，3）（2，4）……等所有结点
以至于后面所有的结点。
**在这里需要用到一个数组来记录前继结点。 **
这个算法的主要形式就是三层循环。从外到内在这里依次为一，二，三，层循环。
第一层循环是中间结点。
第二层循环0是起始结点
第三层循环是结束结点。
需要定义一个path[][]数组。初始化为每对结点的终止结点，例如（i，j）那就在i，j对应的path数组中对应的值为j。
初始化path数组如下：
image.png
三层循环如下：
image.png
代码如下；
//
// main.cpp
// Floyd
//
// Created by 橘子和香蕉 on 2018/12/15.
// Copyright © 2018 橘子和香蕉 All rights reserved.
//
/*
1:求各个顶点之间的最短路径 时间复杂度是n*3
2:从图的邻接矩阵出发，
还是和之前的算法一样，找一个中间结点来更新所有的结点。假如 v到 u最短距离，还有几个结点，比如是m，n，b
遍历这个结点，比如现在用m来更新所有的结点，看距离是不是短的，要是比之前短，就更新，否则，就不要更新，
就是。D（u，v） = min（D（u，v），D（u，m）+D（m，v））
这个算法三层循环，中间结点在最外面的一层。因为这样的才可以以他为中心，来遍历所有的结点
*/
#include <iostream>
using namespace std;
#define VERTEXNUM 100
#define INT_MAX 9999
class Graph{
private:
char vertex[VERTEXNUM];//顶点表
int edge[VERTEXNUM][VERTEXNUM];//边表
int vertexNum;//顶点个数
int edgeNum;//边的个数
int locate(char data);//在顶点表中找data的位置
void initEdge();
public:
Graph(int vertexNum,int edgeNum);
void create();
void Floyd(char start ,char end);
void printGraph();//输出
};
void Graph::printGraph(){
cout<<endl;
cout<<endl;
cout<<"顶点边:\n";
cout<<"vertexNum:"<<vertexNum<<" edgeNum:"<<edgeNum<<endl;
for (int i = 0; i<vertexNum; i++) {
cout<<vertex[i]<<"\t";
}
cout<<endl;
cout<<"边表如下：\n";
for (int j = 0; j<vertexNum; j++) {
for (int k = 0; k<vertexNum ; k++) {
cout<<edge[j][k]<<"\t";
}
cout<<endl;
}
}
int Graph::locate(char data){
for (int i = 0; i<vertexNum;i++) {
if(vertex[i] == data){
return I;
}
}
return -1;
}
Graph::Graph(int vertexNum,int edgeNum){
this->vertexNum = vertexNum;
this->edgeNum = edgeNum;
initEdge();
}
void Graph::create(){
cout<<"input Graph data\n";
for (int i = 0; i<vertexNum; i++) {
cin>>vertex[I];
}
char start ,end;
int wieght = -1;
for (int j = 0; j<edgeNum; j++) {
cout<<"input start and end of edge:\n";
cin>>start>>end>>wieght;
int startPosition = locate(start);
int endPosition = locate(end);
edge[startPosition][endPosition] = wieght;
edge[endPosition][startPosition] = wieght;
}
}
void Graph:: initEdge(){
for (int i = 0; i<vertexNum; i++) {
for (int j =0 ; j<=i; j++) {
edge[i][j] = INT_MAX;
edge[j][i] = INT_MAX;
}
}
for (int i = 0; i<vertexNum; i++) {
for (int j = 0; j<vertexNum; j++) {
cout<<edge[i][j]<<"\t";
}
cout<<endl;
}
}
void Graph::Floyd(char start,char end){
int path[vertexNum][vertexNum];//定义路径数组
for (int i = 0; i<vertexNum; i++) {//初始化，默认i到j的中间结点是j
for (int j = 0; j<vertexNum; j++) {
path[i][j] = j;
}
}
for (int k = 0; k < vertexNum; k++) {
for (int i = 0; i < vertexNum; i++) {
for (int j = 0; j < vertexNum; j++) {
if( edge[i][k]+edge[k][j] < edge[i][j]){
edge[i][j] = edge[i][k]+edge[k][j];
path[i][j] = path[i][k];
}
}
}
}
cout<<"每一对顶点的路径如下";
int k = -1;
for (int i = 0; i < vertexNum; i++) {
for (int j = i+1; j < vertexNum; j++) {
cout<<"<"<<vertex[i]<<":"<<vertex[j]<<">\t";
k = path[i][j];
cout<<vertex[i]<<"\t";
while (k != j) {
cout<<vertex[k]<<"\t";
k = path[k][j];
}
cout<<endl;
}
}
cout<<endl;
cout<<"path如下\n";
for (int i = 0; i < vertexNum; i++) {
for (int j = 0; j < vertexNum; j++) {
cout<<path[i][j]<<"\t";
}
cout<<endl;
}
cout<<"要查找的"<<start<<"到"<<end<<"的路径如下\n";
int startPosition = locate(start);
int endPosition = locate(end);
cout<<"<"<<start<<":"<<end<<">\t"<<start<<"\t";
k = path[startPosition][endPosition];
while (k != endPosition) {
cout<<vertex[k]<<"\t";
k = path[k][endPosition];
}
}
int main(){
Graph a(6, 8);
a.create();
a.printGraph();
a.Floyd('1', '2');
}
path数组中保存的是前一个结点的位置
那怎么输出呢？
如下所示：
测试的时候是上面的图。
例如要查找 1 到 2 的对应的最短路径
先去查找path数组中，1 ，2 对应的值，结果是4，这就说明4是第一个中间结点，继续查找 path 中，4，2对应的项，发现是3，这就说明3是 2 到4 的中间结点。也就是1 到 2 的第二个中间结点，继续查找3 到 2 在path对应的项，发现是2，这就说明没有中间结点了。
输出代码如下：
image.png
这里的图的无向带权图，代码运行结果如下；
image.png
网友评论