floyd.cpp

Floyd最短路径算法的VC7.0试验成功！可以计算2点间的最短路径。

// Floyd.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
using namespace std;

#define   INFINITY   -1   
#define   VERTEX   10   
typedef   int   VRType;   
typedef   char   InfoType;   
typedef   int   VertexType;   
	
typedef  int  PathMatrix[VERTEX][VERTEX];   
typedef  int  DistanceMatrix[VERTEX][VERTEX];   
enum Graphkind {DG,DN,AG,AN}; //{有向图，有向网，无向图，无向网}   
typedef struct ArcCell   
{   
	VRType   adj;   //顶点关系类型，对无权图，用0、1表示是否相邻，对带权图，表示权值类型   
	InfoType   *info;   //该弧相关信息的指针　   
}ArcCell,AdjMatrix[VERTEX][VERTEX];   
	
typedef   struct   
{   
	VertexType   vexs[VERTEX]; //顶点向量   
	AdjMatrix   arcs; //邻接矩阵   
	int   vexnum,arcnum; //图的当前顶点数和弧数   
	Graphkind   kind; //图的种类标志   
}MGraph;   
	
MGraph   G;   
PathMatrix   P;   
DistanceMatrix   D; 
//////////////////////////////////////   
void ShortestPath_FLOYD(MGraph G,PathMatrix P,DistanceMatrix &D)   
//用FLOYD算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w].   
//P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点   
{   
	int   v,w,u;   
	for(v=0;v<G.vexnum;v++) //初始化各对顶点之间的路径及距离   
		for(w=0;w<G.vexnum;w++)   
		{   
			D[v][w]=G.arcs[v][w].adj;   
			for(u=0;u<G.vexnum;u++)   
				P[v][w]=v;   
				if(D[v][w]!=INFINITY)   
				{   
				P[v][w]=w;   
				}   
			}   
			for(u=0;u<G.vexnum;u++)   
				for(v=0;v<G.vexnum;v++)   
					for(w=0;w<G.vexnum;w++)   
					{   
						if(D[v][u]!=INFINITY&&D[u][w]!=INFINITY)   
						{   
							if(D[v][w]==INFINITY||D[v][u]+D[u][w]<D[v][w])   
							{   
								D[v][w]=D[v][u]+D[u][w];   
								P[v][w]=u;  
							}  
						}   
					}   
}  

void Input(void)   
{   
	int kind = 2;   
	//cin>>G.vexnum>>G.arcnum>>kind;   
	G.vexnum = 12;
	G.arcnum = 16;
	G.kind=(Graphkind)kind;  

/*	for(int i=0;i<G.vexnum;i++)   
	{   
		for(int j=0;j<G.vexnum;j++)   
		{   
			cin>>G.arcs[i][j].adj;   
			D[i][j]=G.arcs[i][j].adj;   
		}   
	} */  
}   

void   print(int   i,int   j)   
{   
	if(   i<0   ||   i>=G.vexnum   ||   j<0   ||   j>=G.vexnum   )   
	{   
	cout<<"参数错误！\n";   
	return;   
	}   
	cout<<"from   "<<i<<"   to   "<<j<<endl;   
	if(   i==j   )   
	{   
	cout<<"不需要经过中间顶点！\n";   
	return;   
	}   
	if(P[i][j]==i)   
	{   
	cout<<"没有路径\n";   
	return;   
	}   
	cout<<"Passed   through   ";   
	do   
	{   
	cout<<P[i][j]<<"   ";   
	i=P[i][j];   
	}while(   i   !=   j);   
			cout<<endl;   
}   

int _tmain(int argc, _TCHAR* argv[])
{
	Input();   
	ShortestPath_FLOYD(G,P,D);   
	for(int   i=0;   i<G.vexnum   ;i++   )   
  {   
  for(   int   j=0   ;j<G.vexnum   ;j++   )   
  {   
  print(i,j);   
  }   
  }   
	return 0;
}