Floyd算法(C++极简版)

更新时间:2018-06-29 15:34:17点击次数:959次

Floyd算法<伪代码>:

1.初始化权值数组,路径字串

2.依次添加各顶点

    2.1判断是否存在经由所添顶点产生的小路径

        2.1.1更新权值数组和路径字串组

源码:

#include<iostream>

#include<iomanip>//控制格式
#include<string>


#define INF 0x3f3f3f3f//定义无穷大
using namespace std;


#define vertexNum 5//源点数
int G[vertexNum][vertexNum];//邻接矩阵
string vertex[]={"A","B","C","D","E"};//源点字符串组
void CreateMGraph()
{
    for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
    {
        if(i==j) G[i][j]=0;
        else G[i][j]=INF;
    }
    G[0][1]=13;G[0][3]=4;
    G[1][0]=13;G[1][2]=15;G[1][4]=5;
    G[2][3]=12;
    G[3][0]=4;G[3][2]=12;
    G[4][2]=6;G[4][3]=3;
}
void Floyd()
{
    int dist[vertexNum][vertexNum],i,k,j;//dist为权值存储数组
    string path[vertexNum][vertexNum];
    //cout<<"初始权值数组和路径字符串数组:"<<endl;
    for(i=0;i<vertexNum;i++)
        for(j=0;j<vertexNum;j++)
    {
        dist[i][j]=G[i][j];
        path[i][j]=vertex[i]+"-->"+vertex[j];
      /*  cout<<path[i][j]<<" ";
        if(dist[i][j]!=INF) cout<<dist[i][j]<<endl;
        else cout<<"∞"<<endl;*/
    }
    for(k=0;k<vertexNum;k++)
         for(i=0;i<vertexNum;i++)
          for(j=0;j<vertexNum;j++)
    {
        if((dist[i][k]+dist[k][j]<dist[i][j])&&(dist[i][k]!=INF)&&(dist[k][j]!=INF)&&(i!=j))
        {
            dist[i][j]=dist[i][k]+dist[k][j];
            path[i][j]=path[i][k]+"-->"+vertex[j];
        }
    }
   for(i=0;i<vertexNum;i++)
   {
       cout<<"顶点"<<vertex[i]<<"到各顶点的短路径及权值和"<<endl;
          for(j=0;j<vertexNum;j++)
          {
              cout<<path[i][j]<<" ";
              if(dist[i][j]!=INF) cout<<dist[i][j]<<endl;
              else cout<<"∞"<<endl;
          }
   }
}


int main()
{
    CreateMGraph();//创建邻接矩阵
    cout<<"打印邻接矩阵:"<<endl;
     for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
    {
        if(G[i][j]==INF) cout<<setw(4)<<"∞";
        else cout<<setw(4)<<G[i][j];
        if(j==vertexNum-1) cout<<endl;
    }
    Floyd();
    return 0;

}

截图:

本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责,本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台,网站上部分文章为转载,并不用于任何商业目的,我们已经尽可能的对作者和来源进行了通告,但是能力有限或疏忽,造成漏登,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

  • 项目经理 点击这里给我发消息
  • 项目经理 点击这里给我发消息
  • 项目经理 点击这里给我发消息
  • 项目经理 点击这里给我发消息