经典算法之Dijkstra算法（求图中任意一对顶点间的最短路径）

/************************
author's email:[email protected]
date:2018.1.30
************************/
/*
迪杰斯特拉算法思想：
	设有两个顶点集合S和T,集合S中存放图中已找到最短路径的顶点，集合T存放图中剩余顶点，初始状态时
	集合S中只包含源点v0,然后不断从集合T中选取到顶点v0路径长度最短的顶点Vu并入到集合S中。集合S
	每并入一个新的顶点Vu,都要修改顶点V0到集合T中顶点的最短路径长度值。不断重复此过程，直到集合T
	的顶点全部并入到S中为止。
迪杰斯特拉算法时间复杂度分析：
	由算法代码可知，本算法主要部分为一个双重循环，外层循环内部有两个并列的单层循环，可以在取一个
	循环内的操作作为基本操作，基本操作执行的总次数即为双重循环执行的次数，为n^2次，因此本算法的
	时间复杂度为O(n^2)。
*/
#include<iostream>
#define INF 100//INF为比图中任何权值都大的数
#define maxSize 7   //图的顶点数
#define number 12   //图的边数
using namespace std;
typedef struct {//图的定义
	int edges[maxSize][maxSize];//邻接矩阵的定义
	int n, e;   //分别为顶点数和边数
}MGraph;
MGraph createGraph(MGraph g);
void Dijkstra(MGraph g, int v, int dist[], int path[]);/*迪杰斯特拉算法代码，函数结束时
dist[]存放了v点到其余各顶点的最短路径长度，path[]中保存从V到各顶点的最短路径*/
void printfPath(int path[], int a);//输出起始点v到终点a之间的最短路径
int main() {

	MGraph g;//定义并初始化图g
	g.edges[maxSize][maxSize] = { 0 };
	g.n = maxSize; g.e = number;
	g = createGraph(g);//创建一个图

	int dist[maxSize] = {0};
	int path[maxSize] = {0};
	int v = 0;//起始点
	Dijkstra(g, v, dist, path);

	cout << "顶点"<<v<<"到各顶点的最短路径及最短路径长度为：" << endl;
	for (int i = 1; i < maxSize; ++i)
	{
		printfPath(path, i);
		cout<<"最短路径长度为：" << dist[i]<<endl;
	}
	system("pause");
	return 0;
}

MGraph createGraph(MGraph g) {
	int i, j;
	for (i = 0; i < maxSize; i++)
	{
		for (j = 0; j < maxSize; j++)
		{
			g.edges[i][j] = INF;
		}
	}
	g.edges[0][1] = 4;
	g.edges[1][0] = 4;
	g.edges[0][2] = 6;
	g.edges[2][0] = 6;
	g.edges[0][3] = 6;
	g.edges[3][0] = 6;
	g.edges[1][2] = 1;
	g.edges[2][1] = 1;
	g.edges[1][4] = 7;
	g.edges[4][1] = 7;
	g.edges[2][3] = 2;
	g.edges[3][2] = 2;
	g.edges[2][4] = 6;
	g.edges[4][2] = 6;
	g.edges[2][5] = 4;
	g.edges[5][2] = 4;
	g.edges[3][5] = 5;
	g.edges[5][3] = 5;
	g.edges[4][5] = 1;
	g.edges[5][4] = 1;
	g.edges[4][6] = 6;
	g.edges[6][4] = 6;
	g.edges[6][5] = 8;
	g.edges[5][6] = 8;
	g.n = maxSize;
	g.e = number;
	return g;
}

/*迪杰斯特拉算法代码，函数结束时
dist[]存放了v点到其余各顶点的最短路径长度，path[]中保存从V到各顶点的最短路径*/
void Dijkstra(MGraph g, int v, int dist[], int path[])
{
	int set[maxSize];/*set[]为标记数组，set[Vi]=0表示Vi在T中，即没有被并入最短路径；
					 set[Vi]=1表示Vi在S中，即已经被并入最短路径。*/
	int min, i, j, u;

	//对各数组初始化
	for (i = 0; i < g.n; ++i)
	{
		dist[i] = g.edges[v][i];
		set[i] = 0;
		if (g.edges[v][i] < INF)
			path[i] = v;
		else
			path[i] = -1;
	}
	set[v] = 1; path[v] = -1;//初始化结束

	for (i = 0; i < g.n - 1; ++i)
	{
		min = INF;

		/*这个循环每次从剩余顶点中选出一个顶点，通往这个顶点的路径在通往所有剩余顶点的路径中
		是长度最短的*/
		for (j=0;j<g.n;++j)
		{
			if (set[j] == 0 && dist[j] < min)
			{
				u = j;
				min = dist[j];
			}
		}
		set[u] = 1;//将选出的顶点并入最短路径中

		/*这个循环以刚并入的顶点作为中间点，对所有通往剩余顶点的路径进行检测*/
		for (j = 0; j < g.n; ++j)
		{
			/*这个if语句判断顶点u的加入是否会出现通往顶点j的更短的路径，如果出现，则
			改变原来路径及其长度，否则什么都不做。*/
			if (set[j] == 0 && dist[u] + g.edges[u][j] < dist[j])
			{
				dist[j] = dist[u] + g.edges[u][j];
				path[j] = u;

			}
		}

	}
}
void printfPath(int path[], int a)//输出起始点v到终点a之间的最短路径
{
	int stack[maxSize], top = -1;//定义并初始化栈
	/*这个循环以由叶子节点到根节点的顺序将其入栈*/
	while (path[a] != -1)
	{
		stack[++top] = a;
		a = path[a];
	}
	stack[++top] = a;
	while (top != -1)
	{
		cout << stack[top--] << " ";//出栈并打印出栈元素，实现了顶点的逆序打印
	}
	cout << endl;

}