弗洛伊德算法Floyd-最短路径

似乎没什么说的。。。那就不说了????

注意的是，主对角线上面是0

弗洛伊德是插点的

/*弗洛伊德算法，求每对顶点最短路径*/
#include <malloc.h>
#include <iostream>
#include <cstdio>
using namespace std;
#define  MAX_LEN    20//图最大顶点数
#define  INFINITY   255
typedef  bool    path_table[MAX_LEN][MAX_LEN][MAX_LEN];
typedef  int     dist[MAX_LEN][MAX_LEN];
typedef  struct  graph
{
    int vexnum,arcnum;
    int tyust[MAX_LEN][MAX_LEN];
    char vex[MAX_LEN];
}*Graph;

int get_pos(Graph my_map,char c)
{
    for(int i=0;i<my_map->vexnum;i++)
    {
        if(my_map->vex[i]==c)
        {
            return i;
        }
    }
    return -1;
}
void print(Graph my_map)
{
    for(int i=0;i<my_map->vexnum;i++)
    {
        for(int j=0;j<my_map->vexnum;j++)
        {
            printf("%-4d",my_map->tyust[i][j]);
        }
        cout<<endl;
    }
    cout<<endl;
}
Graph  creat_graph()//创建有向图
{
    char in1,in2;
    int vexnum,arcnum;
    int p1,p2,weiget;
    Graph  pit=(Graph)malloc(sizeof(graph));
    cout<<"请输入顶点数和边数"<<endl;
    cin>>vexnum>>arcnum;
    pit->arcnum=arcnum;
    pit->vexnum=vexnum;


    for(int i=0;i<vexnum;i++)
    {
        for(int j=0;j<vexnum;j++)
        {
            if(i==j)pit->tyust[i][j]=0;
            else pit->tyust[i][j]=INFINITY;
        }
    }


    cout<<"请输入顶点:"<<endl;
    for(int i=0;i<vexnum;i++)
        cin>>pit->vex[i];


    for(int i=0;i<arcnum;i++)
    {
        cout<<"请输入边和权重"<<i+1<<endl;
        cin>>in1>>in2>>weiget;
        p1=get_pos(pit,in1);
        p2=get_pos(pit,in2);
        pit->tyust[p1][p2]=weiget;
    }
    print(pit);
    return pit;
}
void Floyd(Graph pit,path_table p,dist d)
{
    //初始化
    for(int i=0;i<pit->vexnum;i++)
    {
        for(int j=0;j<pit->vexnum;j++)
        {
            d[i][j]=pit->tyust[i][j];
            for(int k=0;k<pit->vexnum;k++)
                p[i][j][k]=false;
            if(d[i][j]<INFINITY)
                p[i][j][i]=p[i][j][j]=true;
        }
    }
    ////////////////////////////////////////
    for(int i=0;i<pit->vexnum;i++)
    {
        for(int j=0;j<pit->vexnum;j++)
        {
            for(int k=0;k<pit->vexnum;k++)
            {
                if(i!=j&&i!=k&&j!=k&&d[j][i]<INFINITY&&d[i][k]<INFINITY&&d[j][i]+d[i][k]<d[j][k])
                {
                    //插入i
                    //更新最小距离
                    d[j][k]=d[j][i]+d[i][k];
                    for(int temp=0;temp<pit->vexnum;temp++)
                    p[j][k][temp]=p[j][i][temp]||p[i][k][temp];//一个为真即是真
                }
            }
        }
    }
}


void make_path(Graph g,bool *p,int i,int j)//路径寻找
{
    int start=i;//start等于开始点也就是0
    int my_min,temp;
    while(start!=j)
    {
        my_min=INFINITY;
        for(int k=0;k<g->vexnum;k++)//寻找最小的，这是符合我们的先前记录的顺序的
        {
            if(g->tyust[start][k]<my_min&&p[k])
            {
                my_min=g->tyust[start][k];
                temp=k;
            }
        }
        if(my_min==INFINITY)break;

        printf("%c",g->vex[temp]);
        if(temp!=j)//不是终点
        printf("->");
        p[temp]=false;//标志
        start=temp;
    }
    cout<<endl;
}
int main()
{
    bool *path;
    path_table p;//三维数组
    dist d;//二维数组
    Graph pit=creat_graph();
    Floyd(pit,p,d);
    path=(bool *)malloc(MAX_LEN*sizeof(bool));
    for(int i=0;i<pit->vexnum;i++)
    {
        for(int j=0;j<pit->vexnum;j++)
        {
            if(i!=j)//不是本身
            {
                cout<<pit->vex[i]<<"->"<<pit->vex[j]<<"  ";
                for(int k=0;k<pit->vexnum;k++)
                {
                    cout<<p[i][j][k]<<"  ";
                    path[k]=p[i][j][k];
                }
                cout<<endl<<"最短路径:"<<d[i][j]<<"  ";
                make_path(pit,path,i,j);
            }
        }
    }
    return 0;
}