【数据结构】什么是图的最短路径？实现最短路径的2种算法？

红太狼 2023-09-26 10:22 87阅读 0赞

## **目录** ##

一、什么是最短路径？

二、实现最短路径的2种算法？

三、最短路径

1、某个顶点到其余各顶点的最短路径：迪 杰斯特拉(Dijkstra)算法

2、每一对顶点之间的最短路径: 佛洛依德(Floyed) 算法

四、练习

--------------------

## 一、什么是最短路径？ ##

**最短路径**问题是指在一个赋权图的两个节点之间找出一个具有**最小权的路径**。旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

> 现实生活中我们可用看到许多最短路径问题的例子：
> 
> 1.  如公交车辆的最优行驶路线和旅游线路的选择。
> 2.  军事领域中，作战部队的行军陆路线。
> 3.  救护车、消防车等救援车辆采取最短行驶路线火速赶往现场。

以上等问题，都是在寻找一个的最短路径作为最优选择；而这就与寻找一个图的最短路径密切相关。

--------------------

## 二、实现最短路径的2种算法？ ##

用于解决最短路径问题的算法被称做“**最短路径算法**”， 有时被简称作“路径算法”。

最常用的路径算法有：

> **1、迪 杰斯特拉(Dijkstra)算法：**
> 
> 求单源最短路径的。
> 
> 从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用[贪心算法][Link 1]的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

> **2、佛洛依德(Floyed) 算法：**
> 
> 是解决任意两点间的最短路径的一种算法，用来求图中所有点对之间的最短路径。

## 三、最短路径 ##

> ### 1、某个顶点到其余各顶点的最短路径：**迪 杰斯特拉(Dijkstra)算法** ###

#### **1）概述** ####

*  网经常用于描述一个城市或城市间的交通运输网络。
    
     *  以顶点表示一个城市或某个交通枢纽
     *  以边表示两地之间的交通状况
     *  边上的权值表示各种相关信息
 *  当两个顶点之间存在多条路径时，其中必然存在一条“最短路径”
 *  名词：
    
     *  源点（Source）：路径中的第一个顶点
     *  终点（Destination）：最后一个顶点

#### **2）实例** ####

![852cd0b35fed45378b0febf4682418fb.png][]

从源点**v0到终点v5**存在多条路径：

> v0, v5) 的长度为 100
> 
> (v0, v4, v5) 的长度为 90
> 
> (v0,v4,v3 v5) 的长度为 60 //最短路径
> 
> (v0, v2,v3, v5) 的长度为 7

从源点v0到各终点的最短路径：

> v0到终点v1不存在路径
> 
> (v0,v2) 的最短路径长度为10
> 
> (v0,v4,v3) 的最短路径长度为50
> 
> (v0,v4) 的最短路径长度为30
> 
> (v0,v4,v3,v5) 的最短路径长度为60

#### **3）迪杰斯特拉(Dijkstra)算法：概述** ####

*  算法描述：
    
    > 1.用于求解**某个源点到其余各顶点**的最短路径。
    > 
    > 2.按最短路径长度递增的次序求解
    > 
    > 3.类似于普利姆算法
 *  每一条最短路径必定只有两种情况：
    
    > 1.由源点直接到达终点
    > 
    > 2.只经过已经求得最短路径的顶点到达终点
 *  迪杰斯特拉算法解决的问题：如何实现“按最短路径长度递增的次序”求解
 *  解决方法：
    
    > 1.每次选出当前的一条最短路径
    > 
    > 2.算法中需要引入一个辅助向量D，它的每个分类D\[i\]存放当前所找到的从源点到各个终点vi的最短路径长度。

#### **4）迪杰斯特拉(Dijkstra)算法：算法分析** ####

> 1.  初始若从源点v到各个终点有弧，则存在一条路径，路径长度即为该弧上的权值，保存于D中
> 2.  求得一条到达某个终点的最短路径，即当前路径中的最小值，该顶点即为w
> 3.  检查是否存在经过顶点w的其他路径，若存在，判断其长度是否比当前求得的路径长度短，若是，则修改D中当前最短路径。
> 4.  重复上面的2和3

![c9294c5f711347e29f30559d53510f45.png][]

#### **5）迪杰斯特拉(Dijkstra)算法：代码实现** ####

测试数据：

![1c101b168b344626bdbbaec2c95f4daa.png][]

处理后的数组P的内容：

![274003da2225468d8271c9f05b6b5214.png][]

处理后数组D的内容：

![81fe24df81404ecd9b410cf49bb8f41a.png][]

**算法代码实现：**

public class ShortestPath_DIJ {
       private boolean[][] P;// v0到其余顶点的最短路径, 若P[v][w]为true，则w是从v0到v当前求得最短路径上的顶点
    
       private int[] D;// v0到其余顶点的带权长度
    
       public final static int INFINITY = Integer.MAX_VALUE;
    
       // 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其权值D[v]
       public void DIJ(MGraph G, int v0) {
          int vexNum = G.getVexNum();
          P = new boolean[vexNum][vexNum];	// 用于记录经过的顶点
          D = new int[vexNum];				// 用于记录到达某顶点需要的最短路径和
          boolean[] finish = new boolean[vexNum];// finish[v]为true当且仅当v属于S,即已经求得从v0到v的最短路径
           
          // 数据初始化
          for (int v = 0; v < vexNum; v++) {
             finish[v] = false;
             D[v] = G.getArcs()[v0][v];		// D 记录v0到所有各个边的权值
             for (int w = 0; w < vexNum; w++)
                P[v][w] = false;			// 设空路径，及设置默认值
             if (D[v] < INFINITY) {
                P[v][v0] = true;			// 在P数组的第v行，标记v0被访问
                P[v][v] = true;				// 在P数组的第v行，标记邻接点被访问
             }
          }
    
          D[v0] = 0;// 初始化，v0顶点属于S集
          finish[v0] = true;
          int v = -1;
    
          // 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集
          for (int i = 1; i < vexNum; i++) {// 其余G.getVexNum-1个顶点
             int min = INFINITY;// 当前所知离v0顶点的最近距离
             for (int w = 0; w < vexNum; w++)
                if (!finish[w])
                   if (D[w] < min) {
                      v = w;
                      min = D[w];
                   }
             finish[v] = true;// 离v0顶点最近的v加入S集
    
             for (int w = 0; w < vexNum; w++)
                // 更新当前最短路径及距离
                if (!finish[w] && G.getArcs()[v][w] < INFINITY
                      && (min + G.getArcs()[v][w] < D[w])) { // 修改D[w]和P[w],w属于V-S
                   D[w] = min + G.getArcs()[v][w];
                   // w在v的基础上继续前行，所以将v经过的内容拷贝到w上
                   System.arraycopy(P[v], 0, P[w], 0, P[v].length);
                   P[w][w] = true;
                }
          }
       }
    
       public int[] getD() {
          return D;
       }
    
       public boolean[][] getP() {
          return P;
       }
       
       public static void main(String[] args) throws Exception {
          MGraph G = GenerateGraph.generateMGraph();
          ShortestPath_DIJ dij = new ShortestPath_DIJ();
          dij.DIJ(G, 0);
          dij.display(G);
       }
    
       // 用于输出最短路径上的各个顶点及权值
       public void display(MGraph G) throws Exception {
          if (D != null) {
             System.out.println("各个顶点到v0的最短路径上的点及最短距离分别是：");
             for (int i = 0; i < P.length; i++) {
                System.out.print("v0 - " + G.getVex(i) + ": ");
                for (int j = 0; j < P[i].length; j++) {
                   if (P[i][j])
                      System.out.print(G.getVex(j) + "\t");
                }
                System.out.println("最短距离为： " + D[i]);
             }
          }
       }
    
    }
    
    // 调试结果：
    // 各个顶点到v0的最短路径上的点及最短距离分别是：
    // v0 - v0: v0 最短距离为： 0
    // v0 - v1: v0 v1 最短距离为： 7
    // v0 - v2: v0 v2 最短距离为： 1
    // v0 - v3: v0 v3 最短距离为： 5
    // v0 - v4: v0 v2 v4 最短距离为： 7
    // v0 - v5: v0 v2 v5 最短距离为： 5

#### **6）迪杰斯特拉(Dijkstra)算法：性能分析** ####

>  *  算法的时间复杂度：O(n2)
>  *  找一条从源点到某一特定终点之间的最短路径问题和求源点到各个终点的最短路径一样复杂，其时间复杂度仍为O(n2)
>  *  若希望得到图中任意两个顶点之间的最短路径，只要依次将每一个顶点设为源点，并调用迪杰斯特拉算法，其时间复杂度为 O(n3)

--------------------

> ### 2、每一对顶点之间的最短路径: **佛洛依德(Floyed) 算法** ###

#### 1）概述 ####

*  若希望得到图中任意**两个定点之间**的最短路径，只要依次将每一个定点设为源点，调用迪杰斯克拉算法n次便可求得，其时间复杂度为O(n3) 。
 *  佛洛依德（Floyed)提出了另外一个算法，虽然时间复杂度也是O(n3），但是算法的形式更为简单。

#### 2）佛洛依德(Floyed) 算法：概述 ####

*  D是路径长度序列
 *  P是路径序列
    
    > 1. 求的一个n阶方阵序列：D(-1)，D(0)，D(1)，D(2)，... ，D(k)，...，D(n-1)
    > 
    > 2. D(-1)\[i\]\[j\]表示从顶点vi出发，不经过其他顶点【直接】到达顶点vj的路径长度。
    > 
    > 3. D(k)\[i\]\[j\]表示从顶点vi到vj的中间只可能经过v0,v1,....,vk , 而不可能经过 vk+1，vk+2， ... ，vn-1等顶点的最短路径长度。
    > 
    > 4. D(n-1)\[i\]\[j\]表示从顶点vi到顶点vj的最短路径的长度。

#### **3）佛洛依德(Floyed) 算法：算法分析** ####

*  **算法关键操作**

// k 表示在路径中新增的顶点号
    // i 表示路径的源点
    // j 表示路径的终点
    if(D[i][k] + D[k][j] < D[i][j]) {
        D[i][j] = D[i][k] + D[k][j];		//更新最短路径长度
        P[i][j] = P[i][k] + P[k][j];		//更新最短路径
    }

*  有向图

![a092d64323e74fce9a2cf5226ec1e583.png][]

#### 4）佛洛依德(Floyed) 算法：代码实现 ####

*  类似于对每一个顶点进行迪杰斯特拉算法。

![fbca0edaa1b444a48520a581c10fae2b.png][]

*  算法代码实现：

public class ShortestPath_FLOYD {
       private boolean[][][] P;// 顶点v和w之间的最短路径P[v][w]，若P[v][w][u]为true，则u是从v到w当前求得最短路径上的顶点
    
       private int[][] D;// 顶点v和w之间最短路径的带权长度D[v][w]
    
       public final static int INFINITY = Integer.MAX_VALUE;
    
       // 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其权值D[v]
       public void FLOYD(MGraph G) {
          int vexNum = G.getVexNum();
          P = new boolean[vexNum][vexNum][vexNum];
          D = new int[vexNum][vexNum];
          for (int v = 0; v < vexNum; v++) // 各对结点之间初始化已知路径及距离
             for (int w = 0; w < vexNum; w++) {
                D[v][w] = G.getArcs()[v][w];
                for (int u = 0; u < vexNum; u++)
                   P[v][w][u] = false;
                if (D[v][w] < INFINITY) {// 从v到w有直接路径
                   P[v][w][v] = true;
                   P[v][w][w] = true;
                }
             }
          for (int u = 0; u < vexNum; u++)
             for (int v = 0; v < vexNum; v++)
                for (int w = 0; w < vexNum; w++)
                   if (D[v][u] < INFINITY && D[u][w] < INFINITY
                         && D[v][u] + D[u][w] < D[v][w]) { // 从v经u到w的一条路径最短
                      D[v][w] = D[v][u] + D[u][w];
                      for (int i = 0; i < vexNum; i++)
                         P[v][w][i] = P[v][u][i] || P[u][w][i];
                   }
       }
    
       public int[][] getD() {
          return D;
       }
    
       public boolean[][][] getP() {
          return P;
       }
    }

*  测试程序：

public class Example6_5_G9 {
    	public final static int INFINITY = Integer.MAX_VALUE;
    
    	public static void main(String[] args) throws Exception {
    		Object vexs[] = { "v0", "v1", "v2" };
    		int[][] arcs = { { 0, 4, 11},
    						{ 6, 0, 2},
    						{ 3, INFINITY,0}};
    		MGraph G = new MGraph(GraphKind.DN, vexs.length, 5, vexs, arcs);
    		ShortestPath_FLOYD floyd = new ShortestPath_FLOYD();
    		floyd.FLOYD(G);
    		display(floyd.getD());
    
    	}
    
    	// 输出各村的最短路径长度
    	public static void display(int[][] D) {
    		System.out.println("各顶点之间的最短路径长度为：");
    		for (int v = 0; v < D.length; v++) {
    			for (int w = 0; w < D.length; w++)
    				System.out.print(D[v][w] + "\t");
    			System.out.println();
    		}
    	}
    
    }
    // 调试结果：
    //各顶点之间的最短路径长度为：
    //		0	4	6
    //		5	0	2
    //		3	7	0

#### **5）佛洛依德(Floyed) 算法：性能分析** ####

>  *  算法复杂度仍为O(n3)
>  *  是解决任意两点间的最短路径的一种算法
>  *  求单源点无负边最短路径用Dijkstra，而求所有点最短路径用Floyd且Floyd可以处理带负边的图。
>  *  对于稀疏的图，采用n次Dijkstra比较出色，对于茂密的图，可以使用Floyd算法。
>  *  从它的三层循环可以看出，它的复杂度是n3，除了在第二层for中加点判断可以略微提高效率，几乎没有其他办法再减少它的复杂度。

--------------------

## 四、练习 ##

**1、迪杰斯特拉(Dijkstra)算法练习：**

![90eca4e584a74b3cae31f32b8ead4e48.png][]

> ①②③④⑤⑥⑦⑧
> 
> (①,②) 最短路径：4
> 
> (①,④) 最短路径：2
> 
> (①,④,③) 最短路径：3
> 
> (①,④,③,⑤) 最短路径：6
> 
> (①,④,③,⑦) 最短路径：6
> 
> (①,④,③,⑤,⑥) 最短路径：8
> 
> (①,④,③,⑤,⑧) 最短路径：18

**2、佛洛依德(Floyed) 算法练习：**

![4f16933f07fe44b284ebd9918ff03191.png][]

推导过程：

![992e0c4cef7f4a529df6702f5410a5de.png][]

[Link 1]: https://baike.baidu.com/item/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/5411800?fromModule=lemma_inlink
[852cd0b35fed45378b0febf4682418fb.png]: https://img-blog.csdnimg.cn/852cd0b35fed45378b0febf4682418fb.png
[c9294c5f711347e29f30559d53510f45.png]: https://img-blog.csdnimg.cn/c9294c5f711347e29f30559d53510f45.png
[1c101b168b344626bdbbaec2c95f4daa.png]: https://img-blog.csdnimg.cn/1c101b168b344626bdbbaec2c95f4daa.png
[274003da2225468d8271c9f05b6b5214.png]: https://img-blog.csdnimg.cn/274003da2225468d8271c9f05b6b5214.png
[81fe24df81404ecd9b410cf49bb8f41a.png]: https://img-blog.csdnimg.cn/81fe24df81404ecd9b410cf49bb8f41a.png
[a092d64323e74fce9a2cf5226ec1e583.png]: https://img-blog.csdnimg.cn/a092d64323e74fce9a2cf5226ec1e583.png
[fbca0edaa1b444a48520a581c10fae2b.png]: https://img-blog.csdnimg.cn/fbca0edaa1b444a48520a581c10fae2b.png
[90eca4e584a74b3cae31f32b8ead4e48.png]: https://img-blog.csdnimg.cn/90eca4e584a74b3cae31f32b8ead4e48.png
[4f16933f07fe44b284ebd9918ff03191.png]: https://img-blog.csdnimg.cn/4f16933f07fe44b284ebd9918ff03191.png
[992e0c4cef7f4a529df6702f5410a5de.png]: https://img-blog.csdnimg.cn/992e0c4cef7f4a529df6702f5410a5de.png