Java数据结构之最短路径

落日映苍穹つ 2022-02-04 02:57 257阅读 0赞

# 问题背景 #

最短路径是面向图的一种非常常见的问题，它是具有实际意义的。比如国家铺铁路，如何使某一个省到其他省的距离最短；或者出去旅游，如何使旅游路线最短。这些问题就是在图的数据结构下求最短路径的问题。通常，求图的最短路径有两种情况，一种是求某一个顶点到其他各顶点的最短路径；另一种是求图中任意两个顶点的最短路径。这里介绍两种算法分别对应上述情况，即迪杰斯特拉算法（Dijkstra算法）和弗洛伊德算法（Floyd算法 ）。

# 迪杰斯特拉算法（Dijkstra算法） #

Dijkstra算法是求某一顶点到其余各顶点最短路径的典型算法。如图1所示，从源点出发，必定存在一条路径，使得源点到终点的距离最短（这里不考虑图的正确性，只考虑算法的思想，读者可以将图中的权值理解为时间而不是距离）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70]

## 核心思想 ##

Dijkstra算法和[Prim算法][Prim]的思想类似，数据结构仍旧是邻接矩阵，因此，我们首先建立图1的邻接矩阵，如图2所示。由邻接矩阵的定义我们可以知道，每一行表示对应顶点到其他顶点的距离（即权值）。

1.  构建数组shortestPath来保存从源点到各顶点的最短路径；
2.  构造标记数组isMatched来记录顶点是否已经算得了最短路径；

> 在Prim算法中，我们定义了lowcost数组用来保存两个顶点之间的最小权值，并通过将权值最小的项置为0来标记当前顶点已经找到了最小权值的边，在不断的迭代后找到最小生成树。可见两者的思想是很相似的。

1.  初始化shortestPath=\{0,1,5,\#,\#,\#,\#,\#,\#\}，并暂时认为shortestPath中的值为源点到其余各点的最短路径；
2.  初始化 isMatched=\{true,false,false,false,false,false,false,false,false\}，isMatched\[0\]=true表示v0点已匹配到最短路径。
3.  定义变量min来记录shortestPath中的最小值，定义变量k来记录该最小值对应的下标，并将isMatched\[k\]置为true，表示vk顶点已匹配到从源点出发的最短路径。

> 拿初始化的shortestPath来说，min=1，k=1，isMatched\[1\]=true，表示从源点v0出发到v1的最短路径为1。此时，尚不能认为v0到v5的最短路径就是5，因为可能存在更短的路径。从图1可以看出，v0–>v1–>v5的距离比v0–>v5的距离短。因此，我们要从已匹配到最短路径的顶点v1出发，计算出v1和其他顶点的距离与min值的和，并与shortestPath中对应的值进行比较，保存较小的值，比如当前Matrix\[1\]\[2\]+min<shortestPath\[2\]，故更新shortestPath的值为Matrix\[1\]\[2\]+min，即v0到v5的最短路径已经更新了。此时，shortestPath全部更新之后为shortestPath=\{0,1,4,8,6,\#,\#,\#,\#\}。

1.  遍历 v1到v8，更新shortestPath数组的最短路径，并同时更新 isMatched 中的标记。

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

## 代码实现 ##

package Dijkstra;
    
    public class DJL {
    	boolean isMatched[];//用于判断顶点是否已经算得了最短路径
    	int shortestPath[];//存放源点到其余各点的最短路径长
    	int vertexs;//顶点数
    	int Matrix[][];//邻接矩阵
    	
    	public DJL(int[][] Matrix) {
    		vertexs = Matrix.length;
    		isMatched = new boolean[vertexs];//初始化isMatched数组为false
    		shortestPath = new int[vertexs];//初始化shortestPath数组为0
    		this.Matrix = Matrix;
    		for(int i=0;i<vertexs;i++) {
    			shortestPath[i] = Matrix[0][i];//初始化shortestPath数组邻接矩阵第一行
    		}
    		isMatched[0] = true;//源点找到最短路径
    	}
    	
    	public int getPath() {
    		try {
    			int k =0;//从起始点v0开始
    			System.out.println("起始点为："+k);
    			
    			for(int v=1;v<vertexs;v++) {
    				int min = Integer.MAX_VALUE;
    				for(int i=0;i<shortestPath.length;i++) {
    					if(!isMatched[i]&&shortestPath[i]<min) {
    						min = shortestPath[i];//获取当前数组中尚未进行匹配的最小值
    						k = i;//记录最小值点的下标
    					}
    				}
    				isMatched[k] = true;//最小值点已进行匹配
    				System.out.println("途径：" +k);
    				for(int i=0;i<shortestPath.length;i++) {
    					if(!isMatched[i]&&(min+Matrix[k][i])>0&&(min+Matrix[k][i])<shortestPath[i]) {//Matrix[k][i]表示顶点k到顶点i的距离
    						shortestPath[i] = min + Matrix[k][i];//源点到顶点i的最短路径
    					}
    				}
    			}
    			for(int i=0;i<shortestPath.length;i++) {
    				System.out.print(shortestPath[i]+"...");
    			}
    		} catch (IndexOutOfBoundsException e) {
    			System.out.println("角标越界了！");
    		}
    		
    		return vertexs;
    	}

## 测试实例 ##

package Dijkstra;
    
    public class DJLDemo {
    
    	public static void main(String[] args) {
    		int MAX_WEIGHT = Integer.MAX_VALUE;
    		int[][] Matrix = new int[9][];	//邻接矩阵
    		
    		//邻接矩阵初始化
    		Matrix[0] = new int[] {0,1,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
    		Matrix[1] = new int[] {1,0,3,7,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
    		Matrix[2] = new int[] {5,3,0,MAX_WEIGHT,1,7,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
    		Matrix[3] = new int[] {MAX_WEIGHT,7,MAX_WEIGHT,0,2,MAX_WEIGHT,3,MAX_WEIGHT,MAX_WEIGHT};
    		Matrix[4] = new int[] {MAX_WEIGHT,5,1,2,0,3,6,9,MAX_WEIGHT};
    		Matrix[5] = new int[] {MAX_WEIGHT,MAX_WEIGHT,7,MAX_WEIGHT,3,0,MAX_WEIGHT,5,MAX_WEIGHT};
    		Matrix[6] = new int[] {MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,3,6,MAX_WEIGHT,0,2,7};
    		Matrix[7] = new int[] {MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,9,5,2,0,4};
    		Matrix[8] = new int[] {MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,7,4,0};
    		
    		DJL d = new DJL(Matrix);
    		d.getPath();
    	}
    
    }

实例结果：
    起始点为：0
    途径：1
    途径：2
    途径：4
    途径：3
    途径：5
    途径：6
    途径：7
    途径：8
    0...1...4...7...5...8...10...12...16...

# 弗洛伊德算法（Floyd算法 ） #

Floyd算法可以求任意两个顶点的最短路径。求任意两个顶点的最短路径同样可以使用Dijkstra算法，只需将所求顶点设成源点即可，但相比于Floyd算法比较复杂。

## 核心思想 ##

1.  创建n阶方阵d用于保存各顶点之间的最短路径长度，其初始化为邻接矩阵。两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2.  创建三维布尔数组p，用于记录最短路径的两个顶点所经过的顶点。

> 对于每一对顶点 v 和 w，看看是否存在一个顶点 u 使得从 v 到 u 再到 w 比已知的路径更短。如果存在，则说明顶点v到顶点w会经过顶点u。则令p\[v\]\[w\]\[u\] = true，表示顶点v和顶点w的最短路径上有顶点u。同时，更新d\[v\]\[w\]=<v,u>+<u,w>（<i,j>——表示顶点i和j的权值）。

1.  重复步骤2，直到遍历所有顶点。

## 算法实现 ##

package Floyd;
    
    import cho6.MGraph;
    
    public class Floyd {
    	private boolean[][][] p; // p[v][w][u] = true表示顶点v和w之间的最短路径上有顶点u
    	private int[][] d; // d[v][w]表示顶点v和w之间的最短路径长度
    
    	public void getFloydPath(int[][] m) {
    		int vNum = m.length;
    		p = new boolean[vNum][vNum][vNum];
    		d = m;
    
    		for (int v = 0; v < vNum; v++) {
    			for (int w = 0; w < vNum; w++) {
    				for (int u = 0; u < vNum; u++) { // 初始化p数组，即默认所有顶点均不相连
    					p[v][w][u] = false;
    				}
    				if (d[v][w] < Integer.MAX_VALUE) {// 顶点v和w是否直接相连
    					p[v][w][v] = true;
    					p[v][w][w] = true;
    				}
    
    			}
    		}
    
    		for (int u = 0; u < vNum; u++) {
    			for (int v = 0; v < vNum; v++) {
    				for (int w = 0; w < vNum; w++) {
    					if (d[v][u] < Integer.MAX_VALUE && d[u][w] < Integer.MAX_VALUE && d[v][u] + d[u][w] < d[v][w]) {
    						d[v][w] = d[v][u] + d[u][w];
    						for (int i = 0; i < vNum; i++) {
    							p[v][w][i] = p[v][u][i] || p[u][w][i];
    						}
    					}
    				}
    			}
    		}
    	}
    
    	/**
    	 * 获取顶点v和w之间的最短路径
    	 * 
    	 * @param v 起始顶点
    	 * @param w 终点
    	 * @return 最短路径
    	 */
    	public int getPath(int v, int w) {
    		return d[v][w];
    	}
    }

## 测试实例 ##

package Floyd;
    
    public class FloydDemo {
    
    	public static void main(String[] args) {
    		int MAX_WEIGHT = Integer.MAX_VALUE;
    		int[][] Matrix = new int[9][];	//邻接矩阵
    		
    		//邻接矩阵初始化
    		Matrix[0] = new int[] {0,1,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
    		Matrix[1] = new int[] {1,0,3,7,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
    		Matrix[2] = new int[] {5,3,0,MAX_WEIGHT,1,7,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
    		Matrix[3] = new int[] {MAX_WEIGHT,7,MAX_WEIGHT,0,2,MAX_WEIGHT,3,MAX_WEIGHT,MAX_WEIGHT};
    		Matrix[4] = new int[] {MAX_WEIGHT,5,1,2,0,3,6,9,MAX_WEIGHT};
    		Matrix[5] = new int[] {MAX_WEIGHT,MAX_WEIGHT,7,MAX_WEIGHT,3,0,MAX_WEIGHT,5,MAX_WEIGHT};
    		Matrix[6] = new int[] {MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,3,6,MAX_WEIGHT,0,2,7};
    		Matrix[7] = new int[] {MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,9,5,2,0,4};
    		Matrix[8] = new int[] {MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,7,4,0};
    
    		Floyd f = new Floyd();
    		f.getFloydPath(Matrix);
    		int p = f.getPath(4, 3);
    		System.out.println(p);
    	}
    
    }

实例结果：
    2

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70]: /images/20220204/c852c491599649ca9b882eb51a33586c.png
[Prim]: https://blog.csdn.net/weixin_44270248/article/details/89644629
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20220204/69cef5dcbbbf4b6e8256c0520383d186.png