zuiduanlujing.cpp

该程序用来求图的单元最短路径

#include<iostream.h>
const int MAXNUM=10000;
const int NumVertices=5; 
class	Graph{
 private:
    	int Edge[NumVertices][NumVertices];
	int dist[NumVertices];
	int  path[NumVertices];
	int  S[NumVertices];
 public :
	void ShortestPath(int,int);
} ;
    void Graph::ShortestPath(int n,int v){
	for(int i=0;i<n;i++)	{
		dist[i]=Edge[v][i];
		S[i]=0;
		if(i!=v&&dist[i]<MAXNUM)
			path[i]=v;
		else	path[i]=-1;	 }
	S[v]=1; dist[v]=0;
 	

for(i=0;i<n-1;i++)	{
	int min=MAXNUM;int u=v;
	for(int j=0;j<n;j++)
		if(!S[j]&&dist[j]<min)
			{u=j;
			min=dist[j];}
		S[u]=1;
	for(int w=0;w<n;w++)if(!S[w]&&Edge[u][w]<MAXNUM&&dist[u]+Edge[u][w]<dist[w]){
		dist[w]=dist[u]+Edge[u][w];
 		path[w]=u;}
	}
}

#include<iostream.h>
#include"graph.h"
void main()
{   int m,n;
	cout<<"请输入图的顶点数："<<endl;
	cin>>n;
	cout<<"请输入图的边数："<<endl;
	cin>>m;
	int a[50][50];
	int b[50];
	int c[50];

	cout<<"请输入图的边，第一个数据为起点，第二个数是中点，第三个是这条边的权值："<<endl;
	for(int i=0;i<n;i++)
		cin>>b[i];
	    cin>>c[i];
		for(int j=0;j<n;j++)
			cin>>a[i][j];
    ShortestPath(n,1);
	cout<<endl;
}