www.pudn.com > XiaoYuanDaoYouTu.rar > Floyd.cpp

#include  
#include "Graphm.h" 
#include "Stock.h" 
 
char getView(int number); 
 
void Floyd(Graph& G, int **D,int proV,int nextV) 
{ 
	int i,j,v;                 //i,j是计数器，v记录相应顶点 
	 
	int** p = new int* [G.VerticesNum()]; //定义一个路径矩阵来保存经过的点 
 
	for (int n=0; n(D[i][v]+D[v][j]) 
	for(v=0;v (D[i][v]+D[v][j])) 
				{ 
					D[i][j]=D[i][v]+D[v][j]; 
					p[i][j] = v; 
				}	 
			} 
		} 
	} 
	/*-----输出最短路径的长度------*/ 
	cout << endl; 
	cout << "("; 
	getView(proV); 
	cout << ")"; 
	cout << "和"; 
	cout << "("; 
	getView(nextV); 
	cout << ")"; 
	cout << "之间的最短距离为:"; 
	cout << D[proV][nextV] << endl; 
 
	/*------定义一个栈来保存最短路径所经过的景点------*/ 
 
	Stock st(10); 
	int mid = -1; 
	st.push(nextV); 
	while (mid != proV) 
	{ 
		mid = p[proV][nextV]; 
 
		if (mid != proV) 
		{ 
			st.push(mid); 
		} 
 
		nextV = mid; 
	} 
	st.push(proV); 
 
	/*------输出最短路径------*/ 
 
	cout << endl; 
	cout << "其间通过的景点如下:" << endl; 
	for (i=st.m_nTop; i>-1; --i) 
	{ 
		cout << getView(st.pop()) << "----"; 
	} 
	cout << endl; 
 
	/*------消亡路径矩阵--------*/ 
 
	for (n=0; n