【最短路径问题（Shortest Path）——图】

Myth丶恋晨 2022-12-21 03:07 189阅读 0赞

### 最短路径问题（Shortest Path） ###

*  一、最短路径（Shortest Path）
 *  二、迪杰斯特拉（Dijkstra)算法
 *   *   *  1、Dijkstra算法基本思想
         *  2、存储结构（顶点个数为n)
         *  3、算法思想
         *  4、算法描述
 *  三、非洛伊德（Floyd)算法
 *   *   *  1、Floyd算法基本思想
         *  2、算法描述

# 一、最短路径（Shortest Path） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]**注意：最短路径与最小生成树不同，路径上不一定包含n个顶点。**

**对于图来说：从一个顶点到另一个顶点可能存在多条路径，每条路径的所包含的边数可能不同。把所包含的边数最少的那条称为最短路径  
最短路径：对于网（带权的图）来说，从一个顶点到另一个顶点所经过的边的权值之和称为带权路径长度，把带权路径长度最短的那条称为最短路径。**

**图可以认为是所有边的权值均为1的网。  
源点：路径上的第一个顶点  
终点：路径上的最后一个顶点**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]

# 二、迪杰斯特拉（Dijkstra)算法 #

**从某个源点到其余各顶点的最短路径——迪杰斯特拉（Dijkstra)算法**

### 1、Dijkstra算法基本思想 ###

![\*\*1、初始化：\*\*][1]

### 2、存储结构（顶点个数为n) ###

**1、主要存储结构：邻接矩阵G\[n\]\[n\] (或者邻接表)  
2、辅助存储结构：  
（1）数组S\[n\]:记录相应顶点是否已被确定最短距离，true：确定；false:未确定**  
**（2）数组D\[n\]:记录源点到相应顶点路径的长度  
初值：如果v0到vi有弧，则D\[i\]为弧上权值，否则为无穷  
（3）数组Path\[n\]:记录相应顶点的前驱顶点  
初值：如果v0到vi有弧，则Path\[i\]为v0,否则为-1**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]

### 3、算法思想 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]

### 4、算法描述 ###

/*迪杰斯特拉算法*/
    void ShortestPath_DIJ(AMGraph G, int v0)
    {
         //用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径
    	n = G.vexnum;//n为G中顶点的个数
    	for (v = 0;v < n;++v)
    	{
         //n个顶点依次初始化
    		S[v] = false; //S初始为空集
    		D[v] = G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始化
    		if (D[v] < MaxInt)
    			Path[v] = v0; //v0与v之间有弧，将v的前驱置为v0
    		else
    			Path[v] = -1; //如果v0与v之间无弧，则将v的前驱置为-1
    	}
    	S[v0] = true; //将v0加入S
    	D[v0] = 0; //源点到源点的距离为0
    	/*初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集*/
    	for (i = 1;i < n;++i)
    	{
         //对其余n-1个顶点，依次进行计算
    		min = MaxInt;
    		for(w = 0;w < n;++w)
    			if (!S[w] && D[w] < min)
    			{
        
    				v = w;
    				min = D[w];
    			} //选择一条当前的最短路径，终点为v
    		S[v] = true; //将v加入S
    		for(w = 0;w < n;++w) //更新从v0出发到集合V-S上所有顶点的最短路径长度
    			if (!S[w] && D[v] + G.arcs[v][w] < D[w])
    			{
        
    				D[w] = D[v] + G.arcs[v][w];//更新D[w]
    				Path[w] = v;//更改w的前驱为v
    			}
    	}
    }

# 三、非洛伊德（Floyd)算法 #

**每一对顶点之间的最短路径——非洛伊德（Floyd)算法**

### 1、Floyd算法基本思想 ###

**从图的带权邻接矩阵G.arcs出发:  
假设求顶点vi到顶点vj的最短路径。如果从vi到vj有弧，则从vi到vj存在一条长度为G.arcs\[i\]\[j\]的路径，但该路径是否是最短路径，还需要进行n次试探。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 9]

### 2、算法描述 ###

void ShortestPath_Floyed(AMGraph G)
    {
         //用Floyed算法求有向网G中各对顶点i和j之间的最短路径
    	for (i = 0;i < G.vexnum;++i) //对各结点之间初始化已知路径及距离
    		for (j = 0;j < G.vexnum;++j)
    		{
        
    			D[i][j] = G.arcs[i][j];
    			if (D[i][j] < MaxInt && i != j)
    				Path[i][j] = i;//i和j之间有弧，将j的前驱置为i
    			else
    				Path[i][j] = -1; //i和j之间无弧，则将j的前驱置为-1
    		}
    	for (k = 0;k < G.vexnum;++k)
    		for (i = 0;i < G.vexnum;++i)
    			for (j = 0;j < G.vexnum;++j)
    				if (D[i][k] + D[k][j] < D[i][j])
    				{
         // 从i经过k到j的一条路径更短
    					D[i][j] = D[i][k] + D[k][j];//更新D[i][j]
    					Path[i][j] = Path[k][j];//更改j的前驱为k
    				}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6130c16082ad4a4c831482745c681f87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/b226d3f17d8e449ab8822d83abb5c4d3.png
[1]: /images/20221120/ba5cbd37d3b9448c8602530be6f751e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201113235753787.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/b7cbc8a0682649a1b092ddcc0e6e9e1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/38e6b95dcb864b37a98cb388edf14497.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/7a71b5995355422996928b7d821d9062.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/85842d0b5b904735ad68b27ba61c05bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221120/f8187599094e41fb9118edfe83864386.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201115105625513.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20201115105645958.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx,size_16,color_FFFFFF,t_70#pic_center