本文共 2683 字，大约阅读时间需要 8 分钟。

Floyd算法又称为插点法，是一种利用的思想寻找给定的中多源点之间的算法。

本文给出一种Floyd算法的C++实现。 此算法支持点和边的动态输入，并提供接口说明

 

1 数据结构

• 无向图的存储结构使用邻接矩阵。
• 每条边的权值为这条边上两点之间的距离。

int**  d = NULL; //二维数组，存储任意两点最短路径的权值之和

int**  path = NULL; //二维数组，存储任意两点之间的最短路径

int matrixSize = 0;//图中顶点的个数

int arcSize = 0;//图中边的个数

int isDigraph = 0;//图的类型，是有向图还是无向图

2 接口定义

定义以下接口：

/*初始化存储结构

vertexNum： 顶点的个数

arcNum：边的个数*/

bool init(int vertexNum, int arcNum)

 

/*添加一条边

start： 边的起点

end：边的终点

weight: 边的权重*/

bool addArc(int start, int end, int weight, bool isDigraph = false)

 

/*计算所有顶点之间的最短路径*/

bool calculatePath()

 

/*返回两个点之间的最短路径

start： 路径的起点

end：路径的终点*/

bool getShortestPath(int start, int end)

 

3 源码实现

#include<stdio.h>

#include<stdlib.h> #include<memory.h> #define MAX 10000000

int**  d = NULL;

int**  path = NULL; int matrixSize = 0; int arcSize = 0; int isDigraph = 0; bool init(int vertexNum, int arcNum) {     matrixSize = vertexNum;     arcSize = arcNum;

    d = (int**)malloc(vertexNum * sizeof(int*));

    memset(d, 0, vertexNum * sizeof(int*));     for(int i = 0; i < vertexNum; i++)     {          d[i] = (int*)malloc(vertexNum * sizeof(int));          memset(d[i], 0, vertexNum * sizeof(int));                    for(int j = 0; j < vertexNum; j++)          {              d[i][j] = MAX;          }     }

    path = (int**)malloc(vertexNum * sizeof(int*));

    memset(path, 0, vertexNum * sizeof(int*));     for(int i = 0; i < vertexNum; i++)     {          path[i] = (int*)malloc(vertexNum * sizeof(int));          memset(path[i], 0, vertexNum * sizeof(int));

         for(int j = 0; j < vertexNum; j++)

         {              path[i][j] = -1;          }     }

    return true;

}

bool addArc(int start, int end, int weight, bool isDigraph = false)

{     if(!isDigraph)     {         d[start][end] = weight;         d[end][start] = weight;         path[start][end] = end;         path[end][start] = start;     }     else     {         d[start][end] = weight;         path[start][end] = end;     } }

bool calculatePath()

{     for(int k=0;k<matrixSize;k++)         for(int i=0;i<matrixSize;i++)             for(int j=0;j<matrixSize;j++) {                 if(d[i][k]+d[k][j]<d[i][j]) {                     d[i][j]=d[i][k]+d[k][j];                     path[i][j]=path[i][k];                 }             }

    return true;

}

bool getShortestPath(int start, int end)

{     if ( (start!=end) && (d[start][end] < MAX))     {          printf("%d->%d:%d ,",start,end,d[start][end]);          printf("     path:");          int f = start;          int en = end;          while (f!=en)          {              printf("%d->",f);              f=path[f][en];          }          printf("%d\n",en);          return true;      }      else if( (start!=end) && (d[start][end] >= MAX))      {          printf("%d->%d:NO PATH\n",start,end);          return false;      }

     return false;

}

int main()

{     int i,j,m,n;     int x,y,z;     printf("input vertexNum arcNum isDigraph:\n");     scanf("%d%d%d",&n,&m,&isDigraph);           init(n, m); 

    for(i=0;i<m;i++) {

            printf("input arc with startPoint endPoint weitht:\n");             scanf("%d%d%d",&x,&y,&z);             addArc(x,y,z, isDigraph);     }           calculatePath();

    printf("List all shortest distance and path:\n");

    for(i=0;i<n;i++)     {         for(j=0;j<n;j++)         {             getShortestPath(i, j);         }     }     return 0; }

转载地址：https://blog.csdn.net/lclfans1983/article/details/105391628 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！