dijkstrashortestpath.cpp

货担郎问题

// DijkstraShortestPath.cpp : Defines the entry point for the console application.
// Copyright SongWenqin [e-mail]

#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"
#include "iostream.h"
#define MAXIMUM 32768
#define M 32767

const int NumVertices=6;//图中最大顶点数
const unsigned int V0Start[NumVertices*NumVertices]={0,M,10,M,30,100,
                                            M,0,5,M,M,M,
											10,5,0,50,M,M,
											M,M,50,0,20,10,
											30,M,M,20,0,60,
											100,M,M,10,60,0};
const unsigned int V1Start[NumVertices*NumVertices]={0,M,5,M,M,M,
                                            M,0,10,M,30,100,
											5,10,0,50,M,M,
											M,M,50,0,20,10,
											M,30,M,20,0,60,
											M,100,M,10,60,0};

class Graph{   //图的类定义
private:
		unsigned int Edge[NumVertices][NumVertices];//图的邻接矩阵
		unsigned int dist[NumVertices];//存放从起始顶点到其它顶点的最短路径长度
		int path[NumVertices];//存放在最短路径上该顶点的前一顶点的顶点号
		int S[NumVertices];//已求得的在最短路径上的顶点的顶点号
	   
public:

	    void InitGraphV0Start();
		void InitGraphV1Start();
	    void ChooseStart(int);
		int ShortestPath(int,int);
		void givePath(int,int);
};

int Graph::ShortestPath (int n,int v){
//G是一个具有n个顶点的带权有向图,各边上的权值由Edge[i][j]给出.本算法建立一个数组:
//dist[j],0<=j<n,是源顶点v到顶点j的最短路径长度,同时用数组path[j],0<=j<n,
//存放求到的最短路径.

	int i,j,r;
	for(i=0;i<n;i++){//dist和path数组初始化
		dist[i]=Edge[v][i];//邻接矩阵第v行元素复制到dist中
	
		S[i]=0;//已求出最短路径的顶点集合初始化
		if(dist[i]<MAXIMUM)path[i]=v;
		else path[i]=0;//路径存放数组初始化
					}  

	S[v]=1;dist[v]=0;//顶点v加入顶点集合

	for(i=0;i<n-1;i++){//从顶点v确定n-1条路径
		unsigned int min=MAXIMUM;int u=-1;
		
		for(j=0;j<n;j++)//选择当前不在集合S中具有最短路径的顶点w
			if((S[j]==0)&&(dist[j]<min)){u=j;min=dist[j];}
		if(u==-1)continue;
		S[u]=1;//将顶点u加入集合S,表示它已在最短路径上
		for(int w=0;w<n;w++)//紧缩路径
			if((!S[w])&&(Edge[u][v]!=MAXIMUM)&&(dist[u]+Edge[u][w]<dist[w])){
				dist[w]=dist[u]+Edge[u][w];path[w]=u;
			}

	}
	cout<<"distances from source vertice are:"<<endl;
	for(r=0;r<NumVertices;r++)
			printf("%d ",dist[r]);

	return 1;

}



void Graph::InitGraphV0Start(){
	int k=0,i,j;

	for( i=0;i<NumVertices;i++)
		for(j=0;j<NumVertices;j++)
			Edge[i][j]=V0Start[k++];

}

void Graph::InitGraphV1Start(){
	int k=0,i,j;

	for( i=0;i<NumVertices;i++)
		for(j=0;j<NumVertices;j++)
			Edge[i][j]=V1Start[k++];

}

void Graph::givePath (int s,int d){
	if(s!=d) {givePath(s,path[d]);
	cout<<path[d]<<"->";}
}



void main(){
	char cnt;
	int from=0,to;
	Graph MyGraph0;

	cout<<"Graph0 initializing..."<<endl;
	MyGraph0.InitGraphV0Start();
	MyGraph0.ShortestPath(6,0);
	cout<<endl<<"You want to see the detailed path?(Y or N):";
	cin>>cnt;
	while(cnt=='Y'||cnt=='y'){
		cout<<"To Vertice No.:";
		cin>>to;
			MyGraph0.givePath(from,to);
		cout<<endl<<"You want to see the detailed path?(Y or N):";
		cin>>cnt;
		}

	
	Graph MyGraph1;
	cout<<"Graph1 initializing..."<<endl;
	MyGraph1.InitGraphV1Start();
	MyGraph1.ShortestPath(6,0);
	cout<<endl<<"You want to see the detailed path?(Y or N):";
	cin>>cnt;
	while(cnt=='Y'||cnt=='y'){

		cout<<"To Vertice No.:";
		cin>>to;
			MyGraph1.givePath(from,to);
		cout<<endl<<"You want to see the detailed path?(Y or N):";
		cin>>cnt;
		}




}