floyd.cpp

实现了图的单源最短路径的floyd算法

/*Floyd 算法*/
#include "stdio.h"
#include "stdlib.h"
#define max_vertex_num 10
#define INF 300
typedef struct ArcCell
{  
    int adj;
}ArcCell,AdjMatrix[max_vertex_num][max_vertex_num];
typedef struct 
{  
	char vexs[max_vertex_num];
    AdjMatrix arcs;
    int vexnum,arcnum;
}MGraph;
void MGraph_create(MGraph &);
void MiniSpanTree_Floyd(MGraph);
int A[max_vertex_num][max_vertex_num];
void main()
{   
	MGraph G;
    MGraph_create(G);
    printf("Floyd 算法实现任意一对节点间最短路径的结果为：\n");
	MiniSpanTree_Floyd(G);
}
void MGraph_create(MGraph &G)
{  
    char char_vex[8]="ABCDEFG";
	int  edge1[12]={1,1,1,1,2,2,2,3,4,4,5,6};
	int  edge2[12]={2,3,4,6,4,5,7,6,6,7,7,7};
	int  edgeweight[12]={2,4,7,5,6,3,8,6,1,6,7,6};
	int i,j,v1,v2;
    G.vexnum=7;
    G.arcnum=12;
 for(i=1;i<=G.vexnum;i++)
	{   
	   G.vexs[i]=char_vex[i-1];
	   for(j=1;j<=G.vexnum;j++)
	       G.arcs[i][j].adj=INF;
	}
 for(i=1;i<=G.vexnum;i++)
	      G.arcs[i][i].adj=0;
 for(i=1;i<=G.arcnum;i++)
    {  
	    v1=edge1[i-1];
        v2=edge2[i-1];
        G.arcs[v1][v2].adj=edgeweight[i-1];
        G.arcs[v2][v1].adj=edgeweight[i-1];    
	}
}
void MiniSpanTree_Floyd(MGraph G)
{
    int i,j,k=0;
    printf("\nA(%d)\n",k);
  for(i=1;i<=G.vexnum;i++)
	{   
	    for(j=1;j<=G.vexnum;j++)
		{
			A[i][j]=G.arcs[i][j].adj;
		    printf(" %4d  ",A[i][j]);	 
         }
	   printf("\n");
	} 
    for(k=1;k<G.vexnum;k++)
	{   
		printf("\nA(%d)\n",k); 
        for(i=1;i<=G.vexnum;i++)
		{
			for(j=1;j<=G.vexnum;j++)
			{
                 if(A[i][k]+A[k][j]<A[i][j])
					 A[i][j]=A[i][k]+A[k][j];
			}
		}
        for(i=1;i<=G.vexnum;i++)
		{  
	        for(j=1;j<=G.vexnum;j++)
			{
                printf(" %4d ",A[i][j]);
			}
            printf("\n");
		}
	}  
}