欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Floyd算法——最短路径

程序员文章站 2024-03-16 13:25:40
...

用floyd算法求每对顶点间的最短路

其中:
Floyd算法——最短路径

//创建有向图的邻接矩阵

#include<stdio.h>
//-------------------------图的邻接矩阵存储表示---------------------------
#define MaxInt 32767		//表示极大值,即无穷
#define MVNum 20		//最大顶点数
typedef char VerTexType;		//假设顶点的数据类型为字符型
typedef int ArcType;		//假设边的权值类型为整型
typedef struct
{
	VerTexType vexs[MVNum];		//顶点表
	ArcType arcs[MVNum][MVNum];		//邻接矩阵
	int vexnum,arcnum;		//图当前点数和边数
}AMGraph;


void CreateUDN(AMGraph *G);
int LocateVex(AMGraph G, char v);
void ShortestPath_Floyd(AMGraph G);

int main()
{
	AMGraph G;
	CreateUDN(&G);
	ShortestPath_Floyd(G);
	return 0;
}

//------------------------------采用邻接矩阵创建有向网-----------------------------
void CreateUDN(AMGraph *G)
{
	int i,j,k,w;
	char v1,v2;
	printf("请输入总的顶点数和总边数:");
	scanf("%d %d",&G->vexnum,&G->arcnum);
	getchar();
	printf("请依次输入顶点信息:");
	for(i=0;i < G->vexnum;i++)
		scanf("%c",&G->vexs[i]);
	getchar();
	for(i=0;i<G->vexnum;i++)		//初始化邻接矩阵,权值均设为MaxInt
		for(j=0;j<G->vexnum;j++)
			G->arcs[i][j]=MaxInt;
	for(k=0;k<G->arcnum;k++)
	{
		printf("请输入第%d条边依附的两个顶点:",k+1);
		scanf("%c%c",&v1,&v2);
		getchar();
		i=LocateVex(*G,v1);
		j=LocateVex(*G,v2);		//确定v1,v2在G中的位置,即顶点数组的下标
		printf("请输入第%d条边的权值:",k+1);
		scanf("%d",&w);
		getchar();
		G->arcs[i][j]=w;
	}
	return ;
}

//-----------------------定位函数----------------------
int LocateVex(AMGraph G,char v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
	{
		if(G.vexs[i]==v)
			return i;
	}
}

//----------------------floyd算法求每对顶点间的最短路--------------------
void ShortestPath_Floyd(AMGraph G)
{
	int Path[G.vexnum][G.vexnum],D[G.vexnum][G.vexnum];
	int i,j,k;
	for(i=0;i<G.vexnum;i++)				//对各结点之间初始已知路径及距离
		for(j=0;j<G.vexnum;j++)
		{
			D[i][j]=G.arcs[i][j];
			if(D[i][j]<MaxInt&&i!=j)
                Path[i][j]=i;           //如果i和j之间有弧,则将j的前驱置为i
            else Path[i][j]=-1;         //如果i和j之间没有弧,则将j的前驱置为-1
		}
    for(k=0;k<G.vexnum;k++)
        for(i=0;i<G.vexnum;i++)
            for(j=0;j<G.vexnum;j++)
            if(D[i][k]+D[k][j]<D[i][j])     //从i经k到j的一条路更短
            {
                D[i][j]=D[i][k]+D[k][j];
                Path[i][j]=Path[k][j];      //更新j的前驱为k
            }
    printf("\n--------------------------输出结果-----------------------\n");
    int a[G.vexnum-2];
    int c;
    for(i=0;i<G.vexnum;i++)
        for(j=0;j<G.vexnum;j++)
        {
            if(i==j) continue;
            printf("%c到%c之间的最短距离是:%4d   ",G.vexs[i],G.vexs[j],D[i][j]);
            k=Path[i][j];
            c=0;
            while(k!=i)
            {
                a[c]=k;
                k=Path[i][k];
                c++;
            }
            printf("最短路径为:%c->",G.vexs[i]);
            if(c>0)
            {
                for(c=c-1;c>=0;c--)
                    printf("%c->",G.vexs[a[c]]);
            }
            printf("%c",G.vexs[j]);
            printf("\n");
        }
    return ;
}