数据结构——图——迪杰斯特拉(Dijkstra )算法

女爷i 2023-01-12 12:58 146阅读 0赞

## 数据结构——图——迪杰斯特拉(Dijkstra )算法 ##

这是一个按路径长度递增的次序产生最短路径的算法。它的思路大体是这样的。

比如说要求图7-7-3中顶点v0到顶点v1的最短距离，没有比这更简单的了，答案就是1，路径就是直接v0连线到V1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]

由于顶点V1还与V2、V3、V4连线，所以此时我们同时求得了V0→V1→v2=1+3=4,V0→V1→V3=1+7=8，V0->V1→V4=1+5=6。

现在，我问V0到V2的最短距离，如果你不假思索地说是5，那就犯错了。因为边上都有权值，刚才已经有V0→V1→V2的结果是4，比5还要小1个单位，它才是最短距离，如图7-7-4所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]  
由于顶点V2还与V4、V5连线，所以此时我们同时求得了V0→V2→V4其实就是V0→V1→V2→V4=4+1=5，V0→V2→V5=4+7=11。这里V0→V2我们用的是刚才计算出来的较小的4。此时我们也发现V0→V1→V2→V4=5要比 V0→V1→V4=6还要小。所以V0到v4目前的最小距离是5，如图7-7-5所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]  
当我们要求V0到V3的最短距离时，通向V3的三条边，除了V6没有研究过外，V0→V1→V3的结果是8，而V0→V4→V3=5+2=7。因此，V0到V3的最短距离是7，如图7-7-6所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 3]  
好了，我想你大致明白，这个迪杰斯特拉（Dijkstra）算法是如何干活的了。它并不是一下子就求出了V0到V8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

如果还是不太明白，不要紧，现在我们来看代码，从代码的模拟运行中，再次去理解它的思想。

typedef struct
    {
        
    	VertexType vexs[MAXVEX];   /*顶点表*/
    	EdgeType matirx[MAXVEX][MAXVEX];  /*领边矩阵，可看作边表*/
    
    	int numVertexes, numEdges;    /*图中当前的顶点数和边数*/
    } MGraph;
    
    
    #define MAXVEX 9
    
    #define INFINITY 65535
    
    typedef int Pathmatirx[MAXVEX];  /*用于存储最短路径下标的数组*/
    typedef int ShortPathTable[MAXVEX]; /*用于存储到各点最短路径的权值和*/
    
    /* Dijkstra 算法，求有向图G的V0顶点到其余顶点V 最短路径票P[v]及带权长度D[v]*/
    
    /*P[v] 的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和*/
    void ShortestPath_Dijkstra(MGraph G, int v0, Pathmatirx* P, ShortPathTable* D)
    {
        
    	int v, w, k, min;
    	int final[MAXVEX]; /*final[W]=1 表示求得顶点V0至Vw的最短路径*/
    	for (v=0;v<G.numVertexes;v++) /*初始化数据*/
    	{
        
    		final[v] = 0;  /*全部顶点初始化为未知最短路径状态*/
    		(*D)[v] = G.matirx[v0][v]; /*将与v0点有连线的顶点加上权值*/
    		(*P)[v] = 0;     /*初始化路径数组P为0*/
    	}
    
    	(*D)[v0] = 0;        /*v0至v0路径为0*/
    	final[v0] = 1;        /*v0至v0不需要求路径*/
    
    	/*开始主循环，每次求得v0到某个v顶点的最短路径*/
    	for (v=1;v<G.numVertexes;v++)
    	{
        
    		min = INFINITY;  /*当前所知离v0顶点的最近距离*/
    		for (w=0;w<G.numVertexes;w++)   /*寻找离v0最近的顶点*/
    		{
        
    			if (!final[w]&&(*D)[w]<min)
    			{
        
    				k = w;
    				min = (*D)[w]; /*w顶点离v0顶点更近*/
    			}
    		}
    
    		final[k] = 1;  /*将目前找到的最近的顶点置为1*/
    
    		for (w=0;w<G.numVertexes;w++) /*修正当前最短路径及距离*/
    		{
        
    			/*如果经过v顶点的路径比现在这条路径的长度短的话*/
    
    			if (!final[w]&&(min+G.matirx[k][w]<(*D)[w]))
    			{
        
    				/*说明找到了更短的路径，修改D[w]和P[w]*/
    				(*D)[w] = min + G.matirx[k][w];/*修改当前路径长度*/
    				(*P)[w] = k;
    			}
    		}
    	}
    }

调用此函数前，其实我们需要为图7-7-7的左图准备邻接矩阵MGraph 的G，如图7-7-7的右图,并且定义参数V0为0。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 4]  
1．程序开始运行，第4行final数组是为了V0到某顶点是否已经求得最短路径的标记，如果V0到Vw已经有结果，则 final\[w\]=1。

2．第5~10行，是在对数据进行初始化的工作。此时final 数组值均为0，表示所有的点都未求得最短路径。D数组为所有的点都未求得最短路径。D数组为\{65535,1,5,65535,65535,65535,65535,65535,65535\}。因为V0与V1和V2的边权值为1和5。Р数组全为0，表示目前没有路径。

3．第11行，表示 V0到V0自身，权值和结果为0。D数组为\{0,1,5,65535,65535,65535,65535,65535,65535\}。第12行，表示V0点算是已经求得最短路径，因此final\[0\]=1。此时final数组为\{1,0,0,0,0,0,0,0,0\}。此时整个初始化工作完成。

4．第13～~33行，为主循环，每次循环求得V0与一个顶点的最短路径。因此V从1而不是0开始。

5．第15~23行，先令min为65535的极大值，通过w循环，与D\[w\]比较找到最小值min=1，k=1。

6．第24行，由 k=1，表示与V0最近的顶点是V1，并且由 D\[1\]=1，知道此时V0到V1的最短距离是1。因此将V1对应的 final\[1\]设置为1。此时final 数组为\{1,1,0,0,0,0,0,0,0\}。

7．第25~32行是一循环，此循环甚为关键。它的目的是在刚才已经找到V0与V1的最短路径的基础上，对V1与其他顶点的边进行计算，得到V0与它们的当前最短距离，如图7-7-8 所示。因为min=1，所以本来 D\[2\]=5，现在  
V0→V1→V2=D\[2\]=min+3=4，V0→V1→V3=D\[3\]=min+7=8，V0→V1→V4=D\[4\]=min+5=6，因此，D数组当前值为\{0,1,4,8,6,65535,65535,65535,65535\}。而P\[2\]=1，P\[3\]=1，P\[4\]=1，它表示的意思是V0到V2、V3、V4点的最短路径它们的前驱均是V1。此时Р数组值为:\{0,0,1,1,1,0,0,0,0\}。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 5]  
8．重新开始循环，此时i=2。第15～23行，对w循环，注意因为final\[0\]=1和final\[1\]=1，由第18行的!final\[w\]可知，V0与V1并不参与最小值的获取。通过循环比较，找到最小值min=4，k=2。

9．第24行，由k=2，表示已经求出V0到V1的最短路径，并且由 D\[2\]=4，知道最短距离是4。因此将V2对应的final\[2\]设置为1，此时final数组为:\{1,1,1,0,0,0,0,0,0\}。

10．第25~32行。在刚才已经找到V0与V2的最短路径的基础上，对V2与其他顶点的边，进行计算，得到V0与它们的当前最短距离，如图7-7-9所示。因为min=4，所以本来 D\[4\]=6，现在V0→V2→V4=D\[4\]=min+1=5， V0→V2→V5=D\[5\]=min+7=11，因此，D数组当前值为:\{0,1,4,8,5,11,65535,65535,65535\}。而原本P\[4\]=1，此时P\[4\]=2，P\[5\]=2，它表示V0到V4、V5点的最短路径它们的前驱均是V2。此时Р数组值为:\{0,0,1,1,2,2,0,0,0\}。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 6]  
11．重新开始循环，此时i=3。第15~23行，通过对w循环比较找到最小值min=5，k=4。

12．第24行，由k=4，表示已经求出V0到V4的最短路径，并且由D\[4\]=5，知道最短距离是5。因此将V4对应的 final\[4\]设置为1。此时final数组为:\{1,1,1,0,1,0,0,0,0\}。

13．第25～32行。对v4与其他顶点的边进行计算，得到V0与它们的当前最短距离，如图 7-7-10所示。因为min=5，所以本来 D\[3\]=8，现在V0→V4→V3=D\[3\]=min+2=7，本来 D\[5\]=11，现在V0→V4-V5=D\[5\]=min+3=8，另外V0→V4→V6=D\[6\]=min+6=11，V0→V4→V7=D\[7\]=min+9=14，因此，D数组当前值为:\{0,1,4,7,5,8,11,14,65535\]。而原本P\[3\]=1，此时P\[3\]=4，原本P\[5\]=2，此时 P\[5\]=4，另外P\[6\]=4，P\[7\]=4，它表示V0到V3、V5、V6、V7点的最短路径它们的前驱均是V4。此时Р数组值为:\{0,0,1,4,2,4,4,4,0\}。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 7]  
14．之后的循环就完全类似了。得到最终的结果，如图7-7-11所示。此时final数组为:\{1,1,1,1,1,1,1,1,1\}，它表示所有的顶点均完成了最短路径的查找工作。此时D数组为:\{0,1,4,7,5,8,10,12,16\}，它表示V0到各个顶点的最短路径数，比如 D\[8\]=1+3+1+2+3+2+4=16。此时的P数组为:\{0,0,1,4,2,4,3,6,7\}，这串数字可能略为难理解一些。比如P\[8\]=7，它的意思是V0到V8的最短路径，顶点V8的前驱顶点是V7，再由P\[7\]=6表示V7的前驱是V6，P\[6\]=3，表示V6的前驱是V3。这样就可以得到，V0到V8的最短路径为V8<一V7<一V6<一V3一V4<一V2<一V1<一V0，即V0一>V1一>V2一>V4一>V3一>V6→V7—>V8.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 8]  
其实最终返回的数组D和数组P，是可以得到V0到任意一个顶点的最短路径和路径长度的。例如V0到V8的最短路径并没有经过V5，但我们已经知道V0到V5的最短路径了。由D\[5\]=8可知它的路径长度为8，由P\[5\]=4可知V5的前驱顶点是V4，所以V0到V5的最短路径是V0→V1-→V2-→V4→V5。

也就是说，我们通过迪杰斯特拉（Dijkstra）算法解决了从某个源点到其余各顶点的最短路径问题。从循环嵌套可以很容易得到此算法的时间复杂度为O(n2)，尽管有同学觉得，可不可以只找到从源点到某一个特定终点的最短路径，其实这个问题和求源点到其他所有顶点的最短路径一样复杂，时间复杂度依然是O(n2)。

这就好比，你吃了七个包子终于算是吃饱了，就感觉很不划算，前六个包子白吃了，应该直接吃第七个包子，于是你就去寻找可以吃一个就能饱肚子的包子，能够满足你的要求最终结果只能有一个，那就是用七个包子的面粉和馅做的一个大包子。这种只关注结果而忽略过程的思想是非常不可取的。

可如果我们还需要知道如V3到 V5、V1到V7这样的任一顶点到其余所有顶点的最短路径怎么办呢?此时简单的办法就是对每个顶点当作源点运行一次迪杰斯特拉(Dijkstra）算法，等于在原有算法的基础上，再来一次循环，此时整个算法的时间复杂度就成了O(n3)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]: /images/20221119/4aa3c206f5224f18873ddb4a37a389c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/7eba81da9b5746359a241b84556383de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]: /images/20221119/822aec4f710241da90e48682b57204b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 3]: /images/20221119/4e363a415df84572a09dda9b7ac3f1f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 4]: /images/20221119/bbda606ca1dc4c439647faddc796e11d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 5]: /images/20221119/49c2069747504ddf9aafd367bf40ac74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 6]: /images/20221119/c50799f4f25847f3a010aa568b090e49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 7]: /images/20221119/91d4ae04291041c88b1f1e680661b174.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 8]: /images/20221119/83dea9c8b13848588b886c885ea9bb26.png