最短路径.h

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

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

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

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;
    }
}
}

//GraphLib.h

struct RowColWeight{
int cow;
int col;
int wieght;
};
void CreatGarph(AdjMWGraph &G,DataType V[],int n,RowColWeight E[],int e){
for(int i=0;i<n;i++) G.InsertVertex(V[i]);
for(int k=0;k<e;k++) G.InsertEdge(E[k].cow,E[k].col,E[k].wieght);
}
void Printchar(char item)
{
cout<<item<<" ";
}[red]

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

const int MaxListSize=100;
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)const{
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;
}

//SeqQueue.h
#include<assert.h>
#include<iostream>
using namespace std;
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];