最短路径.cpp

本文提出了一种基于矢量角度的最短路径搜索算法

#include "SeqList.h"
#include "SeqQueue.h"

#include<assert.h>
#include<iostream>

using namespace std;
#include<iostream>
#include<stdlib.h>
using namespace std;

const int MaxVertices=10;
const int MaxWeight=10000;

const int MaxListSize=1000;

class AdjMWGraph
{
private:
	SeqList Vertices;
	int Edge[MaxVertices][MaxVertices];
	int numOfEdges;
public:
	AdjMWGraph(const int sz=MaxVertices);
	int GarphEmpty()const
	{
		return Vertices.ListEmpty();
	}
	int NumOfVertices(void)
	{
		return Vertices.ListSize();
	}
	int NumOfEdges(void)
	{
	  return numOfEdges;
	}
	VerT GetValue(const int i);
	int GetWeight(const int v1,const int v2);
	void InsertVertex(const VerT &vertex);
	void InsertEdge(const int v1,const int v2,int weight);
	void DeleteVertex(const int i);
	void DeleteEdge(const int v1,const int v2);
	int GetFirstNeighbor(const int v);
	int GetNextNeighbor(const int v1,const int v2);
	void DepthFirstSearch(const int v,int visited[],void vist(VerT item));
	void BroadFirstSearch(const int v1,int visited[],void visit(VerT item));
	void DepthFirstSearch(void visit(VerT item));
	void BroadFirstSearch(void vist(VerT item));
};

AdjMWGraph::AdjMWGraph(const int sz)
{
	for(int i=0;i<sz;i++)
		for(int j=0;j<sz;j++)
		{
		   if(i==j)Edge[i][j]=0;
		   else Edge[i][j]=MaxWeight;
		}
	  numOfEdges=0;
}

VerT AdjMWGraph::GetValue(const int i)
{
	if(i<0||i>Vertices.ListSize())
	{
	  cerr<<"参数i越界出错!"<<endl;
	  exit(1);
	}
	return Vertices.GetData(i);
}

int AdjMWGraph::GetWeight(const int v1,const int v2)
{
	if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
	{
	  exit(1);
	}
	return Edge[v1][v2];
}

void AdjMWGraph::InsertVertex(const VerT &vertex)
{
	Vertices.Insert(vertex,Vertices.ListSize());
}

void AdjMWGraph::InsertEdge(const int v1,const int v2,int weight)
{
	if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
	{
	  exit(1);
	}
	Edge[v1][v2]=weight;
	numOfEdges++;
}

void AdjMWGraph::DeleteVertex(const int v)
{
	for(int i=0;i<Vertices.ListSize();i++)
	  for(int j=0;j<Vertices.ListSize();j++)
	    if((i==v||j==v)&&Edge[i][j]>0&&Edge[i][j]<MaxWeight)
		{
			Edge[i][j]=MaxWeight;
			numOfEdges--;
		}
	    Vertices.Delete(v);
}

void AdjMWGraph::DeleteEdge(const int v1,const int v2)
{
	if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
		exit(1);
	Edge[v1][v2]=MaxWeight;
	numOfEdges--;
}

int AdjMWGraph::GetFirstNeighbor(const int v)
{
	if(v<0||v>Vertices.ListSize())
		exit(1);
	for(int col=0;col<Vertices.ListSize();col++)
		if(Edge[v][col]>0&&Edge[v][col]<MaxWeight)
			return col;
			return -1;
}

int AdjMWGraph::GetNextNeighbor(const int v1,const int v2)
{
	if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
		exit(1);
	for(int col=v2+1;col<Vertices.ListSize();col++)
	   if(Edge[v1][col]>0&&Edge[v1][col]<MaxWeight)
		return col;
	return -1;
}

void AdjMWGraph::DepthFirstSearch(const int v,int visited[],void visit(VerT item))
{
	visit(GetValue(v));
	visited[v]=1;
	int w=GetFirstNeighbor(v);
	while(w!=-1)
	{
		if(!visited[w]) DepthFirstSearch(w,visited,visit);
			w=GetNextNeighbor(v,w);
	}
}

void AdjMWGraph::BroadFirstSearch(const int v,int visited[],void visit(VerT item))
{
	int u;
	int w;
	SeqQueue queue;
	visit(GetValue(v));
	visited[v]=1;
	queue.EnQue(v);
	while(!queue.IsEmpty())
	{
		  u=queue.DeQue();
		  w=GetFirstNeighbor(v);
		  while(w!=-1)
		  {
			   if(!visited[w])
			   {
				visit(GetValue(w));
				visited[w]=1;
				queue.EnQue(w);
			   }
			w=GetNextNeighbor(u,w);
		  }  
	}
}

void AdjMWGraph::DepthFirstSearch(void visit(VerT item))
{
	int *visited=new int[NumOfVertices()];
	for(int i=0;i<NumOfVertices();i++) visited[i]=0;
	for(int i=0;i<NumOfVertices();i++)
	   if(!visited[i]) 
		   DepthFirstSearch(i,visited,visit);
	delete []visited;
}

void AdjMWGraph::BroadFirstSearch(void visit(VerT item))
{
	int *visited=new int[NumOfVertices()];
	for(int i=0;i<NumOfVertices();i++) 
		visited[i]=0;
	for(int i=0;i<NumOfVertices();i++)
	   if(!visited[i]) 
		   BroadFirstSearch(i,visited,visit);
	delete []visited;
}


//Dijkstra.h
void Dijkstra(AdjMWGraph &G,int v0,int distance[],int path[])
{
	int n=G.NumOfVertices();
	int *s=new int[n];
	int minDis,i,j,u;

	for(i=0;i<n;i++)
	{
		  distance[i]=G.GetWeight(v0,i);
		  s[i]=0;
		  if(i!=v0&&distance[i]<MaxWeight) 
			  path[i]=v0;
		  else path[i]=-1;
	}
	s[v0]=1;
	for(i=1;i<n;i++)
	{
		minDis=MaxWeight;
		for(j=0;j<n;j++)
			if(s[j]==0&&distance[j]<minDis)
			{
				u=j;
				minDis=distance[j];
			}
   
	   if(minDis==MaxWeight) 
		   return;
	   s[u]=1;
	   for(j=0;j<n;j++)
			if(s[j]==0&&G.GetWeight(u,j)<MaxWeight&&distance[u]+G.GetWeight(u,j)<distance[j]){
				distance[j]=distance[u]+G.GetWeight(u,j);
		 path[j]=u;
		}
	}
}




class SeqList
{
//	DataType data[MaxListSize];
	int size;
	public:
	SeqList(void);
	~SeqList(void);
	int ListSize(void)const;
	int ListEmpty(void)const;
//	int Find(DataType &item);
//	DataType GetData(int pos)const;
//	void Insert(const DataType &item,int pos);
//	DataType Delete(const int pos);
	void ClearList(void);
};

SeqList::SeqList(void):size(0){}

SeqList::~SeqList(void){}

int SeqList::ListSize(void)const
{
	return size;
}
int SeqList::ListEmpty(void)const
{
	if(size==0) 
		return 1;
	else return 0;
}
/*int SeqList::Find(DataType &item)
{
	if(size==0) return -1;
	int i=0;
	while(i<size&&item!=data[i])i++;
	return i;
}*/

DataType SeqList::GetData(int pos)
{
	if(pos<0||pos>size-1)
	{
	  cerr<<"参数pos越界!"<<endl;
		 exit(1);
	}
	return data[pos];
}
void SeqList::Insert(const DataType &item,int pos)
{
	if(pos<0||pos>size)
	{
	  cerr<<"参数越界!"<<endl;
		 exit(1);
	}
	if(size==MaxListSize-1)
	{
	  cerr<<"顺序表已经满!"<<endl;
		 exit(1);
	}
	for(int i=size;i>pos;i--)
	  data[i]=data[i-1];

	data[pos]=item;
	size++;
}


DataType SeqList::Delete(const int pos)
{
	if(size==0)
	{
	  cerr<<"顺序表已空无元素可删!"<<endl;
		 exit(1);
	}
	if(pos<0||pos>size-1)
	{
	  cerr<<"参数越界!"<<endl;
		 exit(1);
	}
	DataType temp=data[pos];
	for(int i=pos;i<size-1;i++) 
		data[i]=data[i+1];
	size--;
	return temp;
}


void SeqList::ClearList()
{
	size=0;
}


class SeqQueue{
int rear,front;
DataType *element;
int maxsize;
public:
SeqQueue(){rear=front=0;element=new char[100];}
SeqQueue(int ms);
~SeqQueue(){delete []element;}
bool IsEmpty()const{return rear==front;}
bool IsFull()const{return (rear+1)%maxsize==front;}
int Length()const{return (rear-front+maxsize)%maxsize;}
void EnQue(const &data);
DataType DeQue();
DataType GetNum();
};

SeqQueue::SeqQueue(int ms)
{
	maxsize=ms;
	element=new char[maxsize];
	rear=front=0;
	assert(element!=NULL);
}
void SeqQueue::EnQue(const &data)
{
	assert(!IsFull());
	rear=(rear+1)%maxsize;
	element[rear]=data;
	}

DataType SeqQueue::DeQue()
{
	assert(!IsEmpty());
	front=(front+1)%maxsize;
	return element[front];
}

DataType SeqQueue::GetNum()
{
assert(!IsEmpty());
front=(front+1)%maxsize;
return element[front];