Floyd算法——最短路径
程序员文章站
2024-03-16 13:25:40
...
用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 ;
}
上一篇: Dijkstra最短路算法