main.cpp

最短路径的具体实现

/*************************************************
**主函数实现
*************************************************/
#include "rope.h"

int main()
{
	int n,m,a,b;							//n为图的节点数，m为绳子数，a与b共同确定每一个结点在图中的位置
	int i,j;
	int **q;
	int P[1000][2]={0};						//P为存放每一对中间有长度为1的绳子的结点

	struct MGraph G;
	scanf("%d %d",&n,&m);
	GraphInit(G,n);
	i = j = 0;
	q = (int **)malloc(n*sizeof(int *));	//每一对被拉紧绳子的邻接矩阵，先开列空间，再循环开行空间
	while (i<n)
	{
		*(q+i)=(int *)malloc(n*sizeof(int));
		i++;
	}
/*********************************
**以下为输入部分
**********************************/
	i = j = 0;
	while (i<m)
	{
		scanf("%d %d",&a,&b);
		*(*(G.arcs+a-1)+b-1) = 1;
		*(*(G.arcs+b-1)+a-1) = 1;
		P[i][0]=a-1;						//长度为1的绳子的起点
		P[i][1]=b-1;						//终点
		i++;
	}

	printf("%d\n",ShortestPath_FLOYD(G,q,P,m));//求被拉紧的绳子长度并输出
	return 0;
}