前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >经典算法之最短路径问题

经典算法之最短路径问题

作者头像
用户3467126
发布2019-12-13 15:07:13
2.4K0
发布2019-12-13 15:07:13
举报
文章被收录于专栏:爱编码

定义

所谓最短路径问题是指:如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边的权值总和(称为路径长度)达到最小。最短路径问题一直是图论研究的热点问题。例如在实际生活中的路径规划、地图导航等领域有重要的应用。

重要概念

图的路径:图G =中,从任一顶点开始,由边或弧的邻接至关系构成的有限长顶点序列称为路径。注意:有向图的路径必须沿弧的方向构成顶点序列;构成路径的顶点可能重复出现(即允许反复绕圈)。

路径长度:路径中边或弧的数目。

简单路径:除第一个和最后一个顶点外,路径中无其它重复出现的顶点,称为简单路径。

回路或环:路径中的第一个顶点和最后一个顶点相同时,称为回路或环。

图的最短路径:如果从有向图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。

Dijkstra(迪杰斯特拉)算法

它的算法思想是按路径长度递增的次序一步一步并入来求取,是贪心算法的一个应用,用来解决单源点到其余顶点的最短路径问题。

给定一个带权有向图,再给定图中一个顶点(源点),求该点到其他所有点的最短距离,称为单源最短路径问题。

如下图,求点1到其他各点的最短距离

准备工作:

以下为该题所需要用到的数据

int N; //保存顶点个数

int M; //保存边个数

int max; //用来设定一个比所有边的权都大的值,来表示两点间没有连线

int[] visit; //找到一个顶点的最短距离,就把它设为1,默认为0(即还没有找到)

int[][] distance; //保存图中个边的值,两点间无边则设为max

int[] bestmin; //保存源点到其他各点的最短距离,用于最后输出

String[] path; //有些题目会要求输出路径,保存输出路径

算法步骤:

①找出与源点距离最短的那个点,即遍历distance[1][1],distance[1][2],…distance[1][N]中的最小值,如题:

源点1到2,4,5的距离分别为10,30,100,。3无法直接到达即此时distance[1][3] = max。那么这一步找出的点就是

顶点2。此时distance[1][2]即为源点1到顶点2的最短距离。将visit[2]设为1(顶点2完成)。

②松弛操作,

以①找出的点作为中心点(此时为顶点2),去遍历visit[i]为0的点,如果distance[1][2] + distance[2][i] < distance[1][i]

就把新的较短路径赋值给它,即distance[1][i] = distance[1][2] + distance[2][i],

此时顶点2能到达的点只有顶点3,并且distance[1][3] = max ,所以更新distance[1][3]的值为distance[1][2] + distance[2][3] = 60

完成以上两个步骤后回到步骤①,即这是个循环,每次循环能找出一个最短距离的点和更新其他点,所以该循环要遍历

N-1次就可以把所有点最短距离找出,大概过程如下:

for(int i = 2; i <= N; i++) {

步骤①(在一个循环内找到距离最短的点)

步骤②(以①找到的点为中心,通过一个循环更新所有visit[i]为0的点到源点的距离)

}

完整代码如下:
代码语言:javascript
复制
import java.util.Scanner;
public class Dijkstra__Single_Source_Shortest_Path {

   private static int N;
   private static int M;
   private static int max;
   private static int[] visit;
   private static int[][] distance;
   private static int[] bestmin;
   private static String[] path;
   
   public static void Dijkstra() {
       visit[1] = 1;
       bestmin[1] = 0;
       
       //大循环(搞定这里就算搞定该算法了,后面的输出什么的可以不看)
       for(int l = 2; l <= N; l++) {
           int Dtemp = max;
           int k = -1;
           
           //步骤①
           for(int i = 2; i <= N; i++) {
               if(visit[i] == 0 && distance[1][i] < Dtemp) {
                   Dtemp = distance[1][i];
                   k = i;
               }
           }
           visit[k] = 1;
           bestmin[k] = Dtemp;
           
           //步骤②
           for(int i = 2; i <= N; i++) {
               if(visit[i] == 0 && (distance[1][k] + distance[k][i]) < distance[1][i]) {
                   distance[1][i] = distance[1][k] + distance[k][i];
                   path[i] = path[k] + "-->" + i;
               }
           }
       }
       
       //输出路径
       for(int i=1;i<=N;i++) {
            System.out.println("从"+1+"出发到"+i+"的最短路径为:"+path[i]);
       }
       System.out.println("=====================================");
       for(int i = 1; i <= N; i++) {
           System.out.println("从1出发到" + i + "点的最短距离为:" + bestmin[i]);
       }
   }
   public static void main(String[] args) {
       // TODO Auto-generated method stub

       Scanner input = new Scanner(System.in);
       System.out.print("请输入节点个数N,路径总数M:");
       N = input.nextInt();
       M = input.nextInt();
       max = 10000;
       bestmin = new int[N+1];
       distance = new int [N+1][N+1];
       visit = new int[N+1];
       path=new String[N+1];
       
       for(int i = 1; i <= N; i++) {
           for(int j = 1; j <= N; j++) {
               if(i == j) {
                   distance[i][j] = 0;
               }else {
                   distance[i][j] = max;
               }
           }
           bestmin[i] = max;
           path[i] = new String("1-->" + i);
       }
       
       System.out.println("请输入" + M +"条数据x,y,z(表示x点到y点的距离为z):");
       for(int i = 1; i <= M; i++) {
           int x = input.nextInt();
           int y = input.nextInt();
           int z = input.nextInt();
           distance[x][y] = z;
       }
       input.close();
       
       Dijkstra();
   }

}
运行结果如下:
Floyd(弗洛伊德)算法

Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法,可以正确处理有向图或负权的最短路径问题。(动态规划算法是通过拆分问题规模,并定义问题状态与状态的关系,使得问题能够以递推(分治)的方式去解决,最终合并各个拆分的小问题的解为整个问题的解。)

算法思想

从任意节点i到任意节点j的最短路径不外乎2种可能:

1)直接从节点i到节点j,

2)从节点i经过若干个节点k到节点j。

所以,我们假设arcs(i,j)为节点i到节点j的最短路径的距离,对于每一个节点k,我们检查arcs(i,k) + arcs(k,j) < arcs(i,j)是否成立,如果成立,证明从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短,我们便设置arcs(i,j) = arcs(i,k) + arcs(k,j),这样一来,当我们遍历完所有节点k,arcs(i,j)中记录的便是节点i到节点j的最短路径的距离。(由于动态规划算法在执行过程中,需要保存大量的临时状态(即小问题的解),因此它天生适用于用矩阵来作为其数据结构,因此在本算法中,我们将不使用Guava-Graph结构,而采用邻接矩阵来作为本例的数据结构)

算法分析及描述

假设现要求取如下示例图所示任意两点之间的最短路径:

我们以一个4x4的邻接矩阵(二维数组arcs[ ][ ])作为图的数据结构。比如1号节点到2号节点的路径的权值为2,则arcs[1][2] = 2,2号节点无法直接到达4号节点,则arcs[2][4] = ∞(Integer.MAX_VALUE),则可构造如下矩阵:

根据以往的经验,如果要让任意两个顶点(假设从顶点a到顶点b)之间的距离变得更短,唯一的选择就是引入第三个顶点(顶点k),并通过顶点k中转(a -> k ->b)才可能缩短顶点a到顶点b之间的距离。

于是,现在的问题便分解为:求取某一个点k,使得经过中转节点k后,使得两点之间的距离可能变短,且还可能需要中转两个或者多个节点才能使两点之间的距离变短。比如图中的4号节点到3号节点(4 -> 3)的距离原本是12(arcs[4][3] = 12),如果在只通过1号节点时中转时(4 -> 1 ->3),距离将缩短为11(arcs[4][1] + arcs[1][3] = 5 + 6 = 11)。

其实1号节点到3号节点也可以通过2号节点中转,使得1号到3号节点的路程缩短为5(arcs[1][2] + arcs[2][3] = 2 + 3 = 5),所以如果同时经过1号和2号两个节点中转的话,从4号节点到3号节点的距离会进一步缩短为10。

于是,延伸到一般问题:

1、当不经过任意第三节点时,其最短路径为初始路径,即上图中的邻接矩阵所示。

2、当只允许经过1号节点时,求两点之间的最短路径该如何求呢?只需判断arcs[i][1]+arcs[1][j]是否比arcs[i][j]要小即可。arcs[i][j]表示的是从i号顶点到j号顶点之间的距离,arcs[i][1] + arcs[1][j]表示的是从i号顶点先到1号顶点,再从1号顶点到j号顶点的路程之和。循环遍历一遍二维数组,便可以获取在仅仅经过1号节点时的最短距离,实现如下:

代码语言:javascript
复制
for (int i = 1; i <= vexCount; i++) {
    for (int j = 1; j < vexCount; j++) {
        if (arcs[i][1] + arcs[1][j] < arcs[i][j]) {
            arcs[i][j] = arcs[i][1] + arcs[1][j];
        }
    }
}

由于上述代码更新了两点之间经过1号节点的最短距离arcs[i][j],因此,数组中每两个节点之间对应距离都是最短的。由于此时arcs[i][j]的结果已经保存了中转1号节点的最短路径,此时如果继续并入2号节点为中转节点,则是任意两个节点都经过中转节点1号节点和2号节点的最短路径,因为运算完中转1号节点时,arcs[i][j]的结果已经更新为中转1号节点的最短路径了。

更一般的,继续并入下一个中转节点一直到vexCount个时,arcs[i][j]的结果保存的就是整个图中两点之间的最短路径了。这就是Floyd算法的描述,变成代码就是下面几行行:

代码语言:javascript
复制

for (int k = 1; k <= vexCount; k++) { //并入中转节点1,2,...vexCount
    for (int i = 1; i <= vexCount; i++) {
        for (int j = 1; j < vexCount; j++) {
            if (arcs[i][k] + arcs[k][j] < arcs[i][j]) {
                arcs[i][j] = arcs[i][k] + arcs[k][j];
                path[i][j] = path[i][k]; //这里保存当前是中转的是哪个节点的信息
            }
        }
    }
}

对应到示例图的中间运算结果如下:

代码语言:javascript
复制

print array step of 1: //并入1号节点的结果
    0     2     6     4 
    ∞     0     3     ∞
    7     9     0     1 
    5     7    11     0 

print array step of 2: //并入2号节点的结果
    0     2     5     4 
    ∞     0     3     ∞
    7     9     0     1 
    5     7    10     0 

print array step of 3: //并入3号节点的结果
    0     2     5     4 
   10     0     3     4 
    7     9     0     1 
    5     7    10     0 

print array step of 4: //并入4号节点(图最终两两节点之间的最短路径值)
    0     2     5     4 
    9     0     3     4 
    6     8     0     1 
    5     7    10     0 

虽然此时已求得了节点的最短路径,但结果却不能明显的表达最终最短路径是中转了哪些节点,因此这里对应到动态规划算法中的强项——算法过程中可以完全记录所有的中间结果。我们再定义一个二位数组path[][],其大小规模对应arcs[][],初始结果path[i][j] = j,表示节点i到节点j最后的中转节点是j。在运算中是在判断arcs[i][k]+arcs[k][j]比arcs[i][j]要小时,我们进一步更新为:path[i][j] = path[i][k],即当前最短路径的最后中转节点是path[i][k]对应的节点(如果只允许中专一个节点时即为k,但中转多个节点时,需要对应上一步的中转节点,因此这里要指明是path[i][k]而不是k)。 于是我们通过向前递推path[][]数组,直到path[i][j]是目标节点。则可输出其中转节点,输出函数实现如下:

代码语言:javascript
复制

private void printPath(int arcs[][], int path[][], int vexCount) {
    int temp;
    for (int i = 1; i <= vexCount; i++) {
        StringBuilder builder = new StringBuilder();
        for (int j = 1; j <= vexCount; j++) { //遍历打印任意亮点的路径
            builder.append(i).append("->").append(j)
                .append(", weight: "). append(arcs[i][j])
                    .append(":").append(i);
            temp = path[i][j];
            while(temp != j) {
                builder.append("->").append(temp);
                temp = path[temp][j];
            }
            builder.append("->").append(j).append("\n");
        }
        Log.i(TAG, builder.toString());
    }
}

对应示例图的最短路径的中转节点结果输出如下:

代码语言:javascript
复制

 1->1, weight: 0, path: 1->1
 1->2, weight: 2, path: 1->2
 1->3, weight: 5, path: 1->2->3
 1->4, weight: 4, path: 1->4
 2->1, weight: 9, path: 2->3->4->1
 2->2, weight: 0, path: 2->2
 2->3, weight: 3, path: 2->3
 2->4, weight: 4, path: 2->3->4
 3->1, weight: 6, path: 3->4->1
 3->2, weight: 8, path: 3->4->1->2
 3->3, weight: 0, path: 3->3
 3->4, weight: 1, path: 3->4
 4->1, weight: 5, path: 4->1
 4->2, weight: 7, path: 4->1->2
 4->3, weight: 10, path: 4->1->2->3
 4->4, weight: 0, path: 4->4

具体Floyd算法的示例demo实现,

请参考:https://github.com/Jarrywell/GH-Demo/blob/master/app/src/main/java/com/android/test/demo/graph/Floyd.java

参考文档

https://blog.csdn.net/junya_zhang/article/details/83617762

https://www.jianshu.com/p/92e46d990d17

https://www.cnblogs.com/thousfeet/p/9229395.html

https://www.cnblogs.com/zhanghongcan/p/8684465.html

https://www.cnblogs.com/wangyuliang/p/9216365.html

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-12-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 爱编码 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 重要概念
  • Dijkstra(迪杰斯特拉)算法
    • 准备工作:
      • 算法步骤:
        • 完整代码如下:
          • 运行结果如下:
          • Floyd(弗洛伊德)算法
            • 算法思想
              • 算法分析及描述
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档