rope.cpp

最短路径的具体实现

/*************************************************************************
***头部文件的实现
**************************************************************************/
#include "rope.h"

/***********************************************
**图的初始化
***********************************************/
void GraphInit(struct MGraph &G,int v)
{
	int i,j;
	int **p,*q;
	i = j = 0;
	p = (int **)malloc(v*sizeof(int *));	//开矩阵列向量的空间
	q=(int *)malloc(v*sizeof(int));			//开顶点向量的空间
	while (i<v)
	{
		q[i] = i;				//顶点向量的初始化
		i++;
	}
	G.vexs=q;
	G.vexnum=v;					//置图的顶点数目
	i=0;
	while (i<v)			//矩阵元素的初始化
	{
		*(p+i) = (int *)malloc(v*sizeof(int));	//开矩阵行向量的空间
		while (j<v)
		{
			*(*(p+i)+j)=1002;	//元素初始化为最大值，表示INFINITY
			j++;
		}
		j = 0;
		i++;
	}
	for (i=0;i<v;i++)		//对角线元素初始化为0
	{
		p[i][i]=0;
	}
	G.arcs = p;
}

/***********************************************
**求矩阵中的最大值
***********************************************/
int MatrixMax(int **p,int n)
{
	int i,j;
	int max=0;
	for (i=0;i<n;i++)
	{
		for (j=0;j<n;j++)
		{
			if (max<p[i][j]&&p[i][j]!=1002)
			{
				max=p[i][j];
			}
		}
		
	}
	
	return max;
}

/***********************************************
**求最短路径，即被拉紧绳子的长度
***********************************************/
int ShortestPath_FLOYD(MGraph	G,int  **dist,int P[1000][2],int m)
{
	int u,v,k;
	int a,b;
	int **q;
	q=(int **)malloc(G.vexnum*sizeof(int *));	//q为每对节点之间拉紧绳子的矩阵，开空间
	for (int i=0;i<G.vexnum;i++)
	{
		*(q+i)=(int *)malloc(G.vexnum*sizeof(int));
		for (int j=0;j<G.vexnum;j++)
		{
			q[i][j]=0;							//初始化为0
		}
		
	}
	
	u = v = k = 0;
	for (u = 0; u < G.vexnum; ++u)				//Floyd算法求最短路径的矩阵初始化
	{
		for (v = 0; v < G.vexnum; ++v) 
		{
			dist[u][v] = G.arcs[u][v];
		}
	}

	for (k = 0; k < G.vexnum; ++k)				//Floyd算法求最短路径
	{
		for (u = 0; u < G.vexnum; ++u)
		{
			for (v = 0; v < G.vexnum; ++v)
			{
				if (dist[u][v] > dist[u][k] + dist[k][v])	//从v经k到u的路径更短
				{
					dist[u][v] = dist[u][k] + dist[k][v];	
					                                 // printf(" %d ",k);
				}
			}
		}
	}
/***********************************
**以下处理有非一条最短路径的问题
***********************************/
	u = v = k = 0;
	for (u = 0; u < G.vexnum; ++u)			//三重循环	
	{
		for (v = u+1; v < G.vexnum; ++v)
		{
			for (k = 0; k < m; ++k)
			{
				a = P[k][0];
				b = P[k][1];
				if (dist[u][v] > dist[u][a] + dist[v][b] || dist[u][v] > dist[u][b] + dist[v][a])	//如果绳子被拉紧，a和b为拉紧绳子上长度为1的两个结点
				{												//则必有从u到a和从b到v或者从u到b和从a到v的两段距离之和小于由Floyd算法求出的最短路径长度
					++q[u][v];	//此时相应的矩阵位置加一
					++q[v][u];
					// printf(" %d ",k);
				}
			}
		}
	}
/*							int i,j;
							i = j = 0;
							for (i=0;i<m;i++)
							{
								printf("%d %d\n",P[i][0],P[i][1]);
							}
							i=0;
							while (i<G.vexnum)
							{
								while (j<G.vexnum)
								{
									printf("%d\t",q[i][j]);
									if (j==G.vexnum-1)printf("\n");
									j++;
								}
								j=0;
								i++;
							}*/
	return MatrixMax(q,G.vexnum);
}