欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-15 18:54:36
...
/************************
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;

}