迪杰斯特拉(Dijkstra)算法详解

迪杰斯特拉（Dijkstra）算法详解

在讲解迪杰斯特拉算法之前先讲解一下什么是最短路径：

[图一]

假如我要求从A点到D点的最短路径，我们用肉眼可以很快速找出A–>C–>E–>D就是A点到D点的最最短路径，可是计算机没有肉眼，肉眼也解决不了一些很复杂的图路径问题，这时候我们就要借助计算机了，所以写程序就是要用计算机的思维去考虑问题。

迪杰斯特拉算法是一个按路径长度递增的次序产生最短路径的算法，它不仅能找到指定顶点之间的最短路径还可以把图中其他顶点最短路径一并求出来，理解这一点很重要，因为这反过来恰恰就是迪杰斯特拉算法的核心——在已经找到的最短路径点的基础上找下一个目标点，直到图中所有点被找过一遍。

从上面这段话我们可以得到几个很重要的信息

1.使用该算法的图应该是连通图
2.迪杰斯特拉算法是一个走一步看一步的算法，后面点的最短路径来源于与之相连的
上一个点；
3.图中所有的点只需要遍历一遍

可以说整个算法就是基于上面几个条件产生的，迪杰斯特拉算法的优点也在于这，只需要遍历一遍
所有的点便可以产生最短路径，所以不仅可以使算法时间复杂度降低，并且能得到其他点的最短路径。

具体实现

整个算法围绕那三点产生所以我们给满足这三点准备条件，
条件一第一条可以由自己选择一个连通图实现；
条件二第二条我们可以申请一个图中顶点数目大小的数据，用来保存目标点到各个顶点的最小权值，这里由于图中名字是大写英文字母所以我们可以让A（要求的最短路径的头）占用数组下标为0这个位置，以此类推，该例的数组如下

[图二]
如果你的数组名字是汉子或者其他没有顺序的符号，你可以采用构建一个结构体，里面放上你的顶点名称和你想让这个顶点是几号的标记，在申请一个结构体数组就可以了，在这里我们就直接用这个例子了。
这个例子中我们使用的是A作为开始顶点，所以在程序里第一步我们便需要给上面的权值数组进行赋值，在赋值过程中对于没有直接相连的两个顶点或者目标点和自己重合的点我们赋值为65535并用一个宏MAXLEN表示，表示两个点之间距离“无限远”。这是为了后面代码的简洁性，不用计较这几个点是否真的距离无限远，。（这里附上为什么很多程序会选择用65535作为极值https://blog.****.net/u010412301/article/details/54316640）

所以程序一开始我们会把这个数组【图二中的数组】赋值为下图这个样子
权值图[图三]
从这幅图中我们可以比较直观看出这些顶点到A顶点的权值为多少，有人会发现其实D顶点到A顶点也是有路径的，如经过B顶点就可以到达D顶点，别急，我们可以再增加一个数组用来表示图三中的最短权值路径的前驱顶点是谁，如上图的前驱顶点全是A这个顶点，在数组中他占用0这个位置，所以我们可以得到如下这个数组
前驱顶点图[图四]
条件三到这里我们便可以清楚看出这些顶点对应的前驱顶点是哪一个点，所以这个图三那个数组是要搭配后面这个图四数组才能达到找到最小权值路径的目的的。
刚刚说到的三个准备条件，我们已经完成两个了，还差最后一个，这个就更简单了，只需要申请一个标记数组即可，用来表示该点已经被遍历到，怎样算被遍历到呢，以谁为开始顶点查找下一个与之相邻的点，就可以把他标记为已经遍历，标记数组可申请为下图的样子，其中1表示已经遍历，0表示还未遍历；
标记图[图五]
现在A这个顶点已经遍历了，哪应该把哪一个点作为下一个点进行遍历，以达到全面的查看A点到图中其他顶点的最短权值路径呢？
这就需要转换一下思维了，我们不能眼睛只看到从A顶点到D顶点要先经过C顶点才能达到权值最小，要知道计算机是没有眼睛的，并且前面提到迪杰斯特拉算法还可以得到指点顶点到其他顶点的最小权值路径，不仅仅只得到你想要的目标顶点的最小权值路径，所以在这我们可以先找到从A顶点到下一个顶点我们已知的最短路径，即图三中的最小值，我们很自然找到是B这个顶点，现在我们把B这个顶点标记为已经遍历
标记图

标记完后我们需要更新图三中的权值路径的值，因为此时我们已知道了B顶点证明我们可以从A顶点经过B顶点走到其他点了，如果经过B顶点到其他顶点的权值比图三中对应点的权值小，我们则更改这个位置的权值为小的那个值，并且更新图四的前驱顶点的数据，证明这个最小权值的前驱定顶点是谁，更新完后就是下面这个样子
权值图
前驱顶点图

在这里我们可以解释一下为什么是前驱一个点的图，而不是前驱两个点或者多个点又或者不是下一个点的原因，我们可以清楚看到前驱顶点图中D顶点的前驱是下标为1这个顶点，根据我们的约定，我们知道这个是B顶点，所以我们找到B顶点，我们发现B顶点的前驱顶点为0这个顶点，我们继续找，便会发现下标位0这个顶点正是我们要求最短路径的起始顶点，所以起始我们通过前驱顶点图这一个表中每个元素保存前一个前驱顶点即可得到这个点的所有最小权值路径的前驱顶点。

参照这个流程，我们把剩下的所有顶点全遍历一遍，便可得到下面三个数组里面值的情况

标记图

权值图

前驱顶点图

读者可以自己参照上面那个流程自己推一遍，在这里我提出其中一个流程来详细说一下，帮助读者了解，在我们遍历到E这个顶点时，我们计算从A顶点经过C顶点在经过E顶点后到达D顶点的值比权值数组里原来的值18要小，所以我们更换权值数组里D顶点对应的权值数值，并更新前驱顶点图里D顶点的前驱为E顶点，在数组表示的是下标为4这个顶点；
现在我们便可以轻易得出从A顶点到D顶点的最小权值是多少了，答案是10，路径可以根据前驱顶点图得到是D–>E–>C–>A反过来便是A–>C–>E–>D，同样我们可以得到从A顶点到E顶点的最小权值为5，路径为A–>C–>E；
本例为了讲解容易被理解，选取的连通图比较简单，感兴趣的读者可以自己画几个复杂的图进行验证，只要记住这个流程，不过多复杂的图，一步步来就可以得到最小权值路径了，下面我把代码给贴出来，该代码是用C++语言实现的

#include<iostream>
#include<queue>
using namespase std;


typedef char VertexType;   /*顶点类型由用户定义*/
typedef int EdgeType;     /*边值类型由用户定义*/
#define MAXVEX 10       /*最大顶点数由用户定义*/
#define MAXLEN 65535   /*用65535表示无穷*/

typedef struct nodeo
{
	VertexType vexs[MAXVEX];
	EdgeType   arc[MAXVEX][MAXVEX];
	int numVex,numArc;   
}GMap;

int P[MAXVEX];   //权值数组
int D[MAXVEX];   //前驱顶点数组
bool visited[MAXVEX];  //标记数组

void InitGrp(GMap*);  //创建无向图
void Dijkstra(GMap* map);  //Dijkstra算法
void BFS(GMap* map);    //图的广度遍历，借助栈

int mian()
{
	GMap* map = new GMap;
	InitGrp(map);

	cout<<"广度优先遍历"<<endl;
	BFS(map);

	cout<<endl<<"Dijkstra算法"<<endl;
	Dijkstra(map);

	system("pause"); //防止程序立即退出

	return 0;
}

void InitGrp(GMap* map)
{
	int i,j,k,m;
	char a;

	cout<<"请输入当前顶点数和边数"<<endl;
	cin>>map->numVex>>map->numArc;

	for(i=0;i<map->numVex;i++)
	{
		cout<<"请输入顶点名称:";
		cin>>a;
		map->vexs[i] = a;
	}

	for(i=0;i<map->numVex;i++)
		for(j=0;j<map->numVex;j++)
			map->arc[i][j] = MAXLEN;

	for(i=0;i<map->numArc;i++)
	{
		cout<<"请输入(i,j)的下标i和j与其他们之间边的权值:";
		cin>>k>>m>>j;
		map->arc[k][m] = j;
		map->arc[m][k] = map->arc[k][m];
	}

	return;
}

void Dijkstra(GMap* map)
{
	if(map == NULL)return;

	int i,j,k;
	int min;
	int advjex[MAXVEX];
	
	
	for(i = 0; i<map->numVex;i++)
	{
		D[i] = 0;
		advjex[i] = 1;
		P[i] = map->arc[0][i];
	}

	advjex[0] = 0;
	P[0] = 0;

	for(i = 1;i<map->numVex;i++)
	{
		min = MAXLEN;

		for(j = 0;j<map->numVex;j++)
		{
			if(advjex[j] != 0 && P[j] < min)
			{
				min = P[j];
				k = j;
			}
		}

		advjex[k] = 0;

		for(j = 0;j<map->numVex;j++)
		{
			if(advjex[j] != 0 && ((min + map->arc[k][j]) < P[j]))
			{
				P[j] = min + map->arc[k][j];
				D[j] = k;
			}
		}

	}
	
	return;
}
void BFS(GMap* map)
{
	if(map == NULL)return;

	queue<int> que;
	int i,j;
	for(i = 0;i<map->numVex;i++)
	{
		visited[i] = false;
	}

	for(i = 0;i<map->numVex;i++)
	{
		if(!visited[i])
		{
			visited[i] = true;
			cout<<map->vexs[i]<<endl;
			que.push(i);

			while(!que.empty())
			{
				i = que.front();
				que.pop();
				for(j=0;j<map->numVex;j++)
				{
					if(map->arc[i][j] != MAXLEN  && !visited[j])
					{
						visited[j] = true;
						cout<<map->vexs[j]<<endl;
						que.push(j);
					}
				}
			}
		}

	}
	
	return;
}

到这迪杰斯特拉算法就算讲完了，代码中我顺便粘上了创建图和遍历图的代码，感兴趣的朋友可以研究下这是怎么实现的，最后祝大家在这篇博文中能有所收获，编程道路也能越走越轻松。