shortpath.cpp

一个关于图论的课程设计

#include "iostream.h"
#include <conio.h>

const int max=30000;

const int maxnum = 100;

//创建图类 
class G
{

		int vexNum;							//图中的节点总数 	
		int arcs[maxnum][maxnum];			//图的带权邻接矩阵
		int dist[maxnum];					//图的最短路径权值矩阵
		int path[maxnum];					//用于记录最短路径的前驱顶点
		int s[maxnum];

	public:	
		G()									//构造函数
		{
			vexNum=0;
		}
		
		void initiateArcs(int vex)			//带权邻接矩阵初始化
		{
			vexNum= vex;
			for(int j=0; j<vexNum; j++)
				for(int k=0; k<vexNum; k++)
					cin >> arcs[j][k];
		}
	
		void Shortpath(int v1,int v2  )			 //求任意两点之间的最短路径
		//path[v]为从v0到v的最短路径的前驱顶点，
		//dist[v]为其当前的最短距离.s为全局变量,s[v]=1, 
		//表示v已在S集合中，即已求得从v0到v的最短距离。
		{
			int v;
			for (v=0;  v<vexNum; v++)
			{ 
				s[v]=0; 
				dist[v]=arcs[v1][v];
				if (dist[v]<max)    path[v]=v1;                             //v0是v的前驱
				else    path[v]=-1;                                            //v无前驱
			}
			dist[v1]=0;  
			s[v1]=1;                                                         //S集中开始时只有v0
			
			int i;
			for (i=1; i<vexNum; i++)
			{ 
				int min=max;
				for (int w=0; w<vexNum; w++)
				if (s[w]==0)                                                  //w∈V-S
					if(dist[w] < min) 
					{
						v=w; min=dist[w];
					} 
				s[v]=1;													     //将v加入S
				for(w=0;  w < vexNum; w++)                                      //调整其余在V-S的点
					if(s[w] == 0 && (dist[v] + arcs[v][w] < dist[w]))
					{ 
						dist[w]= dist[v] + arcs[v][w];
						path[w]=v;
					}
				if(v = v2)  
					break;
			}

		}

		void printpath(int v1,int v2)						//打印路径
		{
			cout << "--"<< path[v2];							//运用第归  
			if (v1 != path[v2])
				printpath(v1,path[v2]);
		}

		void printResult ( int v1,int v2)
		{
			cout << "The shortest path between v["<< v1<< "] and v["<< v2<< "] is:";
			cout << v2;
			printpath(v1,v2);

			cout << "\n The value of the shortest path is:";
			cout << dist[v2]<< endl;
		}
};

  

void main()														//主函数  
{

	G graph = G();
	int v1,v2;												//用户输入任意两点
	int vexNum;

	cout << "Input vexNumber  :";							//输入图节点总数
	cin >> vexNum;

	cout << "Input the velueArcs " << endl ;
	graph.initiateArcs(vexNum);								//输入图的带权邻接矩阵

	cout << "Input two vexes:";								//输入任意两个节点
	cin >> v1>> v2;											
	
	graph.Shortpath(v1,v2);									//求出V1、V2之间的最短路径
	graph.printResult(v1,v2);	                            //打印输出结果

	getch();
//	return 1;
}