数据结构——Floyd算法

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构——Floyd算法

橘子和香蕉 2018-12-16 12:37:29 浏览501 评论0

摘要: 算法的思想: 遍历每个结点。然后以这个结点为中间结点来更新所有的结点。edge(I,j) = min( edge( I , k ) + edge( k , j ) , edge( I , j ) )edge就是边的长度例如: 首先 以 1 为中间结点,更新(1,2),(1,3)(1,4...

算法的思想:

遍历每个结点。然后以这个结点为中间结点来更新所有的结点。
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

【云栖快讯】一站式开发者服务,海量学习资源免费学  详情请点击

网友评论