图——Dijkstra算法

最短路径问题

迪杰斯特拉算法
求某一个顶点到其余各顶点的最短路径，也为单元最短路径算法。

Dijkstra1

dict[]数组存储了当前起点到其余各顶点的最短路径长度（是长度，数值），path[]存储了当前起点到其余各顶点的最短路径（是上一个顶点的下标）。set[]标记哪些顶点被选入了最短路径（是标记）。

dict[]数组中，将与其顶点直接相连的顶点的值直接记录下来，与其顶点没有直接相连的点就设为无穷大，自身就设为0。然后通过循环不断的更新其中的值。（存储的是起点和当前未被并入的顶点之间的距离）

path[]存储了顶点到其所在最短路径上前一个顶点的信息 。如果某一个顶点的的path[]数组的值为-1，则说明，在此顶点之前没有其他顶点了。图中1,2,3对应的path[]数组的值为0，则说明1,2,3定点的前一个顶点为0。而4,5,6顶底在path[]数组中的值也为-1，是因为他们现在和当前最短路径上的顶点（现在为初始状态，此时最短路径上只有一个顶点0）没有直接关系。

set[]数组中，当前只有顶点0已经被选为最短路径中的顶点，所以将他标记为1其他的顶点还没有选择，所以暂时都是标记为0。

其中在执行过程中，例如下面这个图中的情况，当前最短路径中一共有0,1,2,3四个顶点，现在要找4,5,6三个顶点中，哪一个距离他们最短。第一个先并的0，然后并入的是1，然后并入的是2，然后并入的是3，看dist[]数组的的长度就知道了，因为都是按照哪个最短就先并哪个顶点的。此时，这里重点讲的是在并入哪一个顶点的比较过程，现在以此举例：在看4顶点，**1.从根结点0到4顶点的距离为4+7（0->1->4）为11，2.**从上一个顶点到4顶点的距离为无穷大（0->3->??),所以更新4顶点的dist[]数组为11，path[]数组为1，因为前一个顶点为1。然后就是再找到5顶点的路径长度是多少，同样要进行上面所说的两个比较，然后再找到6顶点的路径长度是多少，同样比较两个过程，最后，在4,5,6三个结点的路径长度之间选择一个最短的路径，并入最短路径中，将其顶点对应的set[]数组设置为1，就标志为已并入其中。这里，比较的是1.和2.这两种情况，在以后所有的选择哪一个顶点进行并入的时候都是进行这两种情况的比较。
Dijkstra2

接着，这里还有一个注意点，就是如下面的图中的过程，选的是最后一个顶点6怎么并入的过程，第一个路径是从根节点通过中间结点然后到达顶点6，第二个是通过上一个并入的顶点然后到顶点6（对应于上面的1.和2.的过程）对比这两个过程哪个路径短就并入最短路径。但是，有没有想过，第一个路径不止一种路径啊，为什么不这样走呢：0->1->4->6走呢？1,4也都是中间结点啊？？这里就是要讲的注意点就是路径的选择，我们可以以path[]数组为指引，选择路径，我们看0顶点的path[]数组是-1，为根结点的意思，1顶点的path[]数组为0，说明1顶点的前一个顶点为0，所以我们选1，顶点2的path[]为1，所以我们再选2顶点，5顶点的path[]为2，所以我们再选择5顶点，顶点4的path[]为5，所以我们就选择4，最终，选择出0->1->2->5->4这一条路径。其实以path[]作为选择路径的原因是，本来path[]中存储了之前顶点之间最短的路径，你为了保证再接入顶点的路径足够的短，当然前面的路径也要保证是短的。

Dijkstra3

可以看出来，在这个算法中一个核心的步骤就是1.和2.的两个结果的比较。
我们把直接从根结点到要并入的结点v的距离记为dist[v]
通过从上一个已并入的结点到要并入的结点的距离记为dist[vpre]+MGraph[vpre][v]
如果dist[v]>dist[vpre]+MGraph[vpre][v]则更新dist[v]=dist[vpre]+MGraph[vpre][v]更新path[v]=vpre。

代码如下：参数n为图的顶点个数，MGraph[][]为图的边信息，v0为起始顶点,dist[]存最短路径长度，path[]存最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void Dijkstra(int n,float MGraph[][n],int v0,int dist[],int path[]) 
{
	int set[maxSize];  //初始化操作
	int min,v;
	for(int i=0;i<n;++i)
	{
		dist[i]=NGraph[v0][i];
		set[i]=0;
		if(MGraph[v0][i]<INF)
			path[i]=v0;
		else
			path[i]=-1;
	}
	set[v0]=1;path[v0]=-1;
	for(int i=0;i<n-1;++i)  //在没有被并入的顶点中挑一个距离最短路径最近的一个点
	{
		min=INF;
		for(int j=0;j<n;++j)
			if (set[j]==0&&dist[j]<min)
			{
				v=j;
				min=dist[j];
			}
			set[v]=1;  //然后将其设置为1
			for(int j=0;j<n;++j) /此循环是对dist和path数组的更新
			{
				if(set[j]==0
					&&dist[v]+MGraph[v][j]<dist[j])
				{
					dist[j]=dist[v]+MGraph[v][j];
					path[j]=v;
				}
			}
	}
}