图的所有顶点间的最短路径（Floyd算法）

不念不忘少年蓝@ 2023-07-22 12:23 183阅读 0赞

## 问题描述 ##

对每一对顶点vi ≠ vj，求出vi与vj之间的最短路径和最短路径长度

## Floyd算法 ##

Floyd(Floyd-Warshall)算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，该算法名称以创始人之一罗伯特·弗洛伊德命名。  
Floyd-Warshall算法是动态规划的一个例子，即该算法中的前面的运算都会给予后面结果一些影响，下一步得出的结果可能会依赖于上一步得出的结果，运算的整个过程需要层层迭代，最终得出结果。

## 核心思路 ##

**松弛技术**：对在i和j之间的所有其他点进行一次松弛（寻找中间点）

**状态转移方程**： map\[i\]\[j\]=min\{map\[i\]\[k\]+map\[k\]\[j\],map\[i\]\[j\]\}

## 具体运算过程 ##

①建立两个辅助数组：  
a\[ i \]\[ j \]，存储i到j之间的最小路径长度  
path\[ i \]\[ j \]，存储i到j所经历的中间顶点

②辅助数组初始化：使用map\[i\]\[j\]来进行初始化  
若顶点`i`能到达顶点`j`，使得a\[i\]\[j\]=map\[i\]\[j\]，path\[i\]\[j\] = i  
若无法到达，使得a\[i\]\[j\] = MAX，path\[i\]\[j\]=-1(作为标记)

③借助状态转移方程对a\[\]\[\]中所有路径进行松弛  
若图有k个顶点，则需遍历k次，使得每个顶点都可用作中间点进行一次松弛判断  
核心代码：

for(int k=0; k<sMap.num; k++)
       	for(int j=0; j<sMap.num; j++)
        		for(int i=0; i<sMap.num; i++)

④在更新完成之后，所得的两个矩阵即为结果

## 实例 ##

#### 图 ####

![在这里插入图片描述][20200405220911326.png]

#### 矩阵变换 ####

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

## 关于单源路径的提取 ##

##### 问题 #####

在最后得到的结果中，path数组存储着具体的最短路径，但是这个路径只是存储了最短路径途径的一个中间点，而我们还需对中间点在path数组中进行查询才能得出结果

##### 想法 #####

但是应该怎么提取呢，直接中间点在最短路径的位置是不是有什么规律？  
①刚开始，我猜测path\[i\]\[j\]所得直接中间点是在最短路径中距离终点`j`最近的一个中间点，但是在上图中的**2—>1**的直接中间点是4，而最短路径为2–>4–>3–>1，很明显不是；  
②另外对于**1—>4**的直接中间点是4，但最短路径为1–>2–>4–>3，即这个中间点也不是距离源点`i`最近的中间点  
③最终得出这个中间点就是一个最短路径途径得点，既不挨着源点，也不挨着终点，因此在进行路径提取的时候，直接中间点两边都可能有路径

##### 存储结构 #####

为了在路径提取的时候，能够按一个特定的顺序存储，并且可以在两个顶点之间插入一个新的中间点，我使用了**链表**作为存储

##### 具体思路 #####

①在得到源点和终点后先作为链表头和尾形成一个初始结构  
②得到中间点，判断是否还有其他点，没有则结束  
③若有，类似于二叉树的遍历中分别对左右子树处理的方法，使用递归思路，对中间点左右路径都进行处理  
④结束，借助链表输出最短路径

## 具体算法实现 ##

#### 主要算法（包含单源最短路径的输出） ####

/**
      * 分析图，使用floyd算法生成最短路径数组
      * @param sMap
      * @param begin
      * @param end
      */
     public void floyd(SimpleMap sMap, int begin, int end) {
      	//初始化a和path数组
     	this.a = new int[sMap.num][sMap.num];
      	this.path = new int[sMap.num][sMap.num];
      	for(int i=0; i<sMap.num; i++) 
       		for(int j=0; j<sMap.num; j++){
        			a[i][j] = sMap.map[i][j];
        			if(a[i][j] != CreateAMap.MAX && i != j) {
         				path[i][j] = i;
        			}else {
         				path[i][j] = -1;
        			}
       		}
      	//对矩阵进行变化，求得最短路径表
      	//即a[i][k]+a[k][j] < a[i][j]时，将最小路径进行变换
      	for(int k=0; k<sMap.num; k++)
       		for(int j=0; j<sMap.num; j++)
        			for(int i=0; i<sMap.num; i++) {
         				if(a[i][k]+a[k][j] < a[i][j]) {
          					a[i][j] = a[i][k]+a[k][j];
          					//标识最短路径经过k
          					path[i][j] = k;
         				}
        			}
        			
      	//从路径数组中，得到最短路径
      	//初始化路径链表
      	if(path[begin-1][end-1] != -1) {
       		//存在可达路径
       		this.head = new Path();
       		head.data = begin;
       		this.head.nextPath = new Path();
       		this.head.nextPath.data = end;
       		this.head.nextPath.nextPath = null;
       		minPath(begin-1, end-1, this.head);
       
       		//从链表中提取数据
       		System.out.println("从"+begin+"到"+end+"的最短路径为：");
       		System.out.print(this.head.data);
       		Path move = this.head.nextPath;
       		while(move != null) {
        			System.out.print("--->"+move.data);
        			move = move.nextPath;
       		}
       		System.out.println();
       		System.out.println("最短路径长度为："+a[begin-1][end-1]);
      	}else {
       		System.out.println("目标不可达");
      	}
     }

#### 递归求得最短路径 ####

private void minPath(int begin, int end, Path insertNode) {
      	int mid = path[begin][end]; 
      	if(mid != begin) {
       		Path midPath = new Path();
       		midPath.data = mid+1;
       		//连接链表
       		midPath.nextPath = insertNode.nextPath;
       		insertNode.nextPath = midPath;
       		//前半部分
       		minPath(begin, mid, insertNode);
       		//后半部分
       		minPath(mid, end, midPath);
      	}
     }

#### 借助之前的实例，测试结果： ####

![在这里插入图片描述][20200405223621796.png]  
![在这里插入图片描述][20200405223809295.png]

[20200405220911326.png]: /images/20230528/b5718cfa27ac4b359de35e6fb2f55d8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: /images/20230528/683efb6d67f34675b867b91ce335252c.png
[20200405223621796.png]: /images/20230528/0f2f8c5519b14223b3fe3441cf5581ff.png
[20200405223809295.png]: /images/20230528/4770bab53d614002aa3ea58c27c6b561.png