数据结构_图_最短路径_狄杰斯特拉(Dijkstra)算法

此算法没有采用《数据结构C语言版》中的存储结构，而是采用邻接表的方法存储图，经过改进，还能输出最短路径。

"Dijkstra.h"

#include<iostream>
using namespace std;

#define MAX_VEX_NUM 20
#define INFINITY INT_MAX
#define CANTFIND -1

class Path//记录源点到每一个点的路径
{
public:
	Path();
	int pathnode;
	Path *next;
};

Path::Path()
{
	pathnode=0;
	next=NULL;
}

class NextNode//邻接表存储以某节点为尾的弧的相关信息
{
public:
	NextNode();
	int nextvex;//顶点编号
	int weight;//弧上的权值
	NextNode *next;//下一个节点的指针
};

NextNode::NextNode()
{
	nextvex=weight=0;
	next=NULL;
}

class VexNode//顶点相关信息
{
public:
	VexNode();
	char name;//顶点名称
	bool choose;//标示此节点标示的最短路径是否已经被选择
	int dist;//此节点当前存放的最短路径
	NextNode *firstnext;
	Path *path;
};

VexNode::VexNode()
{
	choose=false;
	dist=INFINITY;
	firstnext=NULL;
	path=NULL;
}

class VexBox//顶点集合
{
public:
	VexBox();
	int vexnum;//定点数目
	VexNode vexbox[MAX_VEX_NUM];//顶点集合
};

VexBox::VexBox()
{
	vexnum=0;
}

class ShortestPath_DIJ
{
public:
	void ShortestPath();//接口函数
private:
	void GetVex();//得到顶点信息
	void GetArc();//得到弧的相关信息	
	void GetShortestPath();//得到最短路径
	void PrintShortestPath();//打印最短路径
	int GetShortestNode();//得到dist最小的节点
	void UpdatePath(int,int);//更新路径
	void ReMove(Path *);//销毁原路径
	VexBox v;//顶点集合
	int sourse;
};

void ShortestPath_DIJ::ShortestPath()
{
	GetVex();//得到顶点信息
	GetArc();//得到弧的相关信息	
	GetShortestPath();//得到最短路径
	PrintShortestPath();//打印最短路径
}

void ShortestPath_DIJ::GetVex()//得到顶点信息
{
	cout<<"Please Input The Name Of Each Vertex :"<<endl<<endl;
	char name;
	while(cin>>name)
	{
		v.vexbox[v.vexnum++].name=name;
	}
	cin.clear();
}

void ShortestPath_DIJ::GetArc()//得到弧的相关信息
{
	cout<<"Please Input The Information Of Each Arc :"<<endl
		<<"tail head weight"<<endl;
	int tail,head,weight;
	NextNode *newnode,*p;
	while(cin>>tail>>head>>weight)
	{
		newnode=new NextNode;
		newnode->nextvex=head;
		newnode->weight=weight;
		if((p=v.vexbox[tail].firstnext)==NULL)
		{
			v.vexbox[tail].firstnext=newnode;
		}//if
		else
		{
			while(p->next!=NULL)
				p=p->next;
			p->next=newnode;
		}//else
	}//while
	cin.clear();
}

int ShortestPath_DIJ::GetShortestNode()//得到dist最小的节点
{
	int ans=CANTFIND,min=INT_MAX;
	for(int i=0;i<v.vexnum;i++)
	{
		if(v.vexbox[i].choose==false&&v.vexbox[i].dist<min)
		{
			min=v.vexbox[i].dist;
			ans=i;
		}//if
	}//for
	v.vexbox[ans].choose=true;//标记为已选择
	return ans;
}

void ShortestPath_DIJ::ReMove(Path *p)//销毁原路径
{
	if(p->next!=NULL)
		ReMove(p->next);
	delete p;
}

void ShortestPath_DIJ::UpdatePath(int a,int b)//更新路径
{
	Path *p,*pt,*newpath;
	ReMove(v.vexbox[b].path);
	newpath=new Path;
	newpath->pathnode=v.vexbox[a].path->pathnode;
	v.vexbox[b].path=newpath;
	p=v.vexbox[a].path->next;
	pt=v.vexbox[b].path;
	while(p!=NULL)
	{
		newpath=new Path;
		newpath->pathnode=p->pathnode;
		pt->next=newpath;
		p=p->next;
		pt=pt->next;
	}
}

void ShortestPath_DIJ::GetShortestPath()//得到最短路径
{
	Path *newpath,*pt;
	cout<<"Please Input The Sourse :"<<endl;
	while(cin>>sourse&&!(sourse<v.vexnum));//得到符合条件的源点
	cout<<v.vexbox[sourse].name<<" : Start"<<endl;
	v.vexbox[sourse].dist=0;//对源点的相关处理
	for(int i=0;i<v.vexnum;i++)//初始化路径
	{
		if(i!=sourse)
		{
			newpath=new Path;
			newpath->pathnode=sourse;
			v.vexbox[i].path=newpath;
		}
	}
	NextNode *p;
	p=v.vexbox[sourse].firstnext;
	while(p!=NULL)
	{
		newpath=new Path;
		newpath->pathnode=p->nextvex;
		v.vexbox[p->nextvex].path->next=newpath;
		v.vexbox[p->nextvex].dist=p->weight;
		p=p->next;
	}
	int ncase=v.vexnum-1;
	int node;
	while(ncase--)//处理源点到其他点的最短路径长度
	{
		node=GetShortestNode();//获得当前情况下未被选择的最短边
		if(node==CANTFIND)//控制跳出
			break;
		p=v.vexbox[node].firstnext;
		while(p!=NULL)//如有必要修改和该顶点相关的节点的Dist值
		{
			if(v.vexbox[node].dist+p->weight<v.vexbox[p->nextvex].dist)
			{
				v.vexbox[p->nextvex].dist=v.vexbox[node].dist+p->weight;
				UpdatePath(node,p->nextvex);
				newpath=new Path;
				newpath->pathnode=p->nextvex;
				pt=v.vexbox[p->nextvex].path;
				while(pt->next!=NULL)
					pt=pt->next;
				pt->next=newpath;
			}
			p=p->next;
		}
	}
}

void ShortestPath_DIJ::PrintShortestPath()//打印最短路径
{
	Path *p;
	for(int i=0;i<v.vexnum;i++)
	{
		if(i!=sourse)
		{
			p=v.vexbox[i].path;
			cout<<v.vexbox[i].name<<" : ";
			if(v.vexbox[i].dist==INFINITY)
				cout<<"∞"<<endl;
			else
			{
				cout<<v.vexbox[i].dist<<" Path :";//打印路径
				cout<<v.vexbox[p->pathnode].name;
				p=p->next;
				while(p!=NULL)
				{
					cout<<"->"<<v.vexbox[p->pathnode].name;
					p=p->next;
				}
				cout<<endl;
			}
		}//if
	}//for
}

"mian.cpp"

#include"Dijkstra.h"

int main()
{
	ShortestPath_DIJ d;
	d.ShortestPath();
	system("pause");
}