最短路径-----迪杰特斯拉算法

#include<iostream>
using namespace std;
#define Max 10//最大顶点数
#define MANY 65535
class Graph 
{
private:
	int verNum;//顶点个数
	int arcNum;//边的个数
public:
	int ver[Max];//顶点数组
	int arc[Max][Max];//网图的邻接矩阵
public:
	Graph(int v[],int n,int e);
	int getVernum()
	{
		return verNum;
	}
	int getArcnum()
	{
		return arcNum;
	}
          
};
Graph::Graph(int v[],int n,int e)
{
	verNum = n;
	arcNum = e;
	for (int i = 0; i < verNum; i++)
		ver[i] = v[i];
	for (int i = 0; i < verNum; i++)
	{
		for (int j = 0; j < verNum; j++)
		{
			if (i == j)
			{
				arc[i][j] = 0;
			}
			else {
				arc[i][j] = MANY;
			}
		}
	}
	cout << "请输入每条边依附的两个顶点和权值：" << endl;
	int vi=0, vj=0,k=0;
	for (int i = 0; i <arcNum; i++)
	{
		cin >> vi >> vj>>k;
		arc[vi][vj] = k;
	}
}
//查找当前没有放入s中的最小顶点---dist数组  s数组  顶点数
int findMinDist(int dist[], int s[], int verNum)
{ 
	int min = -1;
	for (int i = 0; i < verNum; i++)
	{
		if (s[i] == 0)//当前节点没有被放入S数组
		{
			 min = i;//假设当前节点为最小顶点
			for (int j = 0; j < verNum; j++)
			{
				if (s[j] == 0)
				{
					if (dist[min] > dist[j])//当前j节点对应dist数组中的值更小，即距离更短
					{
						min = j;
					}
				}
			}
		}
	}
	return min;
}
//打印最短路径
void display(int dist[], int path[],int s[], Graph* p,int startV)
{
	int RightPath[Max] = { 0 };
	for (int i = 0; i < p->getVernum(); i++)
	{
		cout << "源点到" << i << "顶点的最短路径：";
		cout << 0;
		int num = 0;//计算最短路径有几个顶点
		RightPath[num++] = i;
		int t = path[i];
		while (t != 0)
		{
			RightPath[num++] = t;
			t = path[t];
		}
		//逆序打印数组，得到最短路径
		for (int j= num - 1; j>= 0; j--)
		{
			cout << RightPath[j];
		}
		cout << endl;
	}
}
//迪杰斯特拉算法:startV----源点，计算的起点
void Dijkstra(Graph* p, int startV)
{
	int dist[Max];//存放最短路径的长度
	int  path[Max];//存放最短路径的下标
	int s[Max] = { 0 };//S数组中存放的是已经计算出最短路径的节点
	//初始化dist数组和path数组
	for (int i = 0; i < p->getVernum(); i++)
	{
		//当s数组中只有一个源点的时候，那么最短路径就是当前源点到U集合中各顶点的距离
		dist[i] = p->arc[startV][i];
	    //s数组一开始只有一个源点,例如源点为0,0一开始只能到U集合的1 2 3顶点，因此到1,2,3顶点的前一个节点下标为0，因为到4,5,6顶点距离为无穷大，所以无法到达4,5,6，path数组中存放的值为-1
		if (dist[i] != MANY)
		{
			//起点为源点
			path[i] = startV;
		}
		else 
		{
			//源点到达不了该顶点，没有起点
			path[i] = -1;

		}
	}
	//源点放入集合s
	s[startV] = 1;
	//计算当前已经放入S集合中的顶点个数，即已经求出最短路径的节点个数
	int num = 1;//一开始只有源点
	int min = 0;//最小顶点的下标
	while (num < p->getVernum())
	{
		//1.查找当前dist数组中s[i]为0的最小顶点
		min = findMinDist(dist, s, p->getVernum());
		//2.将最小顶点放入集合S中
		s[min] = 1;
		//3.新顶点加入后，是否会产生更优解，如果有就更新dist和path数组
		for (int i = 0; i < p->getVernum(); i++)
		{
			if (s[i] == 0 && dist[i] > dist[min] + p->arc[min][i])
			{
				//更新
				dist[i] = dist[min] + p->arc[min][i];//修改到源点到i顶点最短路径
				path[i] = min;//到达当前i顶点最短路径的前一个起点更新
			}
		}
		num++;
	}
	cout << "path数组打印：" << endl;
	for (int i = 0; i < p->getVernum(); i++)
		cout << path[i] << "\t";
	cout << endl;
	cout << "dist数组打印：" << endl;
	for (int i = 0; i < p->getVernum(); i++)
		cout << dist[i] << "\t";
	cout << endl;
	//打印起始点到各顶点的最短路径
	cout << "打印最短路径：" << endl;
	display(dist,path,s, p,startV);
}
//测试----------------------
void test()
{
	int v[7] = { 0,1,2,3,4,5,6 };
	Graph p(v, 7, 12);
	cout << "打印邻接矩阵" << endl;
	for (int i = 0; i < p.getVernum(); i++)
	{
		for (int j = 0; j < p.getVernum(); j++)
		{
			cout << p.arc[i][j]<<"\t";
		}
		cout << endl;
	}
	Dijkstra(&p, 0);

}
int main()
{
	test();
	system("pause");
	return 0;
}