假期过长,导致停更了好长时间,复习一道算法题找找感觉。
前段时间看到一篇文章,里面提到了统治世界的十大算法,其中之一就是迪杰斯特拉算法(Dijkstra),该算法主要解决的”最短路径“这一类问题。说法虽然夸张了点,但它在实际生活中确实应用广泛,例如地图软件等,大部分游戏中自动寻路等功能,使用到的 A*搜索算法也是基于迪杰斯特拉算法优化而来。那么迪杰斯特拉算法是如何实现的呢?
假如我们现在有如下一个有向图,图中有 6 个顶点,编号分别为 1~6,带有箭头的直线表示的是能从一个顶点到达另外一个顶点,直线上的数字表示的是两个顶点之间的距离,现在求顶点 1 到顶点 6 的最短距离。
由于图中的点比较少,我们直接手动计算就能算出来这个结果,但是如果顶点很多,有成千上万个,手动计算就很难了,我们只能通过程序来计算,那么我们的程序该如何写呢?
思路
从图中我们可以看到,顶点 1 只能直接到达顶点 2、3、5,不能直接到达顶点 6,所以要想从 1 到达 6,就必须得从其他顶点中转。
我们定义一个数组,用来表示每个顶点到顶点 1 的距离,数组的索引表示的是顶点编号,数组元素的值表示的是到顶点 1 的最小距离。
开始我们在顶点 1 上,顶点 1 能到达 2、3、5,数组的状态如下。
从顶点 2 处中转,顶点 2 能到达顶点 4,距离为 35,所以顶点 1 到顶点 4 的距离为 60+35=95,数组状态如下:
从顶点 3 处中转,顶点 3 能到达 4,距离为 30。如果通过顶点 3 中转,那么 1 到达 4 的距离为 40,小于经过 2 中转的距离,所以数组中到顶点 4 的距离更新为 40。顶点 3 还能到达顶点 5,同理,通过顶点 2 中转,1 到达 5 的距离为 10+25=35,小于 1 直接到达 5 的距离,因此数组中到达顶点 5 的距离更新为 35,更新后,数组状态如下:从顶点 5 中转,顶点 5 能到达 2,如果顶点 1 通过顶点 5 到达 2,距离为 35+30=65,大于顶点 1 直接到达 2,所以不更新。由于顶点 2 在前面已经遍历过它能到达哪些点了,所以后面不需要再遍历它。顶点 5 还能到达顶点 6,所以此时 1 到达 6 的距离为 35+105=140,数组状态如下:从顶点 4 中转,顶点 4 也能达到顶点 6。如果通过顶点 4 中转,那么 1 到达 6 的距离为 40+15=55,这个距离小于从 5 中转,所以更新数组,更新后,数组状态如下:
以上流程,就是迪杰斯特拉算法在计算最短路径问题时的核心流程。
代码实现
首先我们需要将这个有向图用代码表示出来,通常表示图的方法有两种:第一种是邻接矩阵(也就是二维数组),第二种是邻接表(也就是数组+链表),这里我们选用邻接表法来表示一个有向图。
另外我们还需要定义顶点之间的边,一条边有起点和终点,还有边的权重信息,也就是长度,用类 Edge 表示。代码如下:
//起始定点 publicints; //终止定点 publicintt; //边的权重 publicintweight; Edge(ints,intt,intweight){ this.s=s; this.t=t; this.weight=weight; } }privateclassEdge{
有向图我们用类 Graph 表示,类中有两个属性:顶点个数 v 和描述顶点之间边的信息的数组 adj,我们还提供了一个方法:addEdge,用来在两个顶点之间添加一条边。代码如下:
//顶点个数(顶点编号从0开始,在本文例子中,编号为0的顶点不存在) privateintv; //记录每个顶点的边 privateLinkedList[]adj;publicGraph(intv){this.v=v;//初始化this.adj=newLinkedList[v];for(inti=0;iadj[i]=newLinkedList(); } }//添加一条边,从s到达tpublicvoidaddEdge(ints,intt,intweight){ Edgeedge=newEdge(s,t,weight); adj[s].add(edge); } }publicclassGraph{
定义好了图的描述信息后,接下来通过代码来实现迪杰斯特拉算法,其代码和注释如下。
有两处逻辑稍微解释一下。第一处:flag 数组记录的是已经遍历过的顶点,用来防止死循环,例如顶点 1 能到达 2,我们接着会判断 2 能到达哪些点,顶点 1 又能到达 5,5 也能到达 2,如果没有 flag 数组来记录顶点 2 我们已经遍历过了,那么我们就会继续遍历 2,这样会导致死循环。第二处:predecessor 数组记录的是路径信息,数组的索引表示的顶点编号,元素的值表示的是哪一个顶点到达当前顶点的,例如:predecessor[3]=1 表示的是通过顶点 1 到达的顶点 3。
publicvoiddijkstra(ints,intt){ int[]dist=newint[v];//记录s到每个顶点的最小距离,数组下标表示顶点编号,值表示最小距离 boolean[]flag=newboolean[v];//记录遍历过的顶点,数组下标表示顶点编号,值表示是否遍历过该顶点 for(inti=0;idist[i]=Integer.MAX_VALUE;//初始状态下,将顶点s到其他顶点的距离都设置为无穷大 } int[]predecessor=newint[v];//记录路径,索引表示顶点编号,值表示到达当前顶点的顶点是哪一个 Queuequeue=newLinkedList<>(); queue.add(s); dist[s]=0;//s->s的路径为0while(!queue.isEmpty()){ Integervertex=queue.poll();if(flag[vertex])continue;//已经遍历过该顶点,就不再遍历 flag[vertex]=true;for(inti=0;iEdgeedge=adj[vertex].get(i);if(dist[vertex]//如果出现了比当前路径小的方式,就更新为更小路径 dist[edge.t]=dist[vertex]+edge.weight; predecessor[edge.t]=vertex; } queue.add(edge.t); } }//打印路径 System.out.println("最短距离:"+dist[t]); System.out.print(s); print(s,t,predecessor); }//采用迪杰斯特拉算法找出从s到t的最短路径
print 函数的作用是打印从顶点 s 到达顶点 t 的最短路径中,需要经过哪些点,具体代码如下,就是一个递归调用,比较简单:
privatevoidprint(ints,intt,int[]predecessor){ if(t==s){ return; } print(s,predecessor[t],predecessor); System.out.print("->"+t); }//打印路径
测试
根据文中的示例,构建一个图,进行结果测试,代码如下:
//构建图 Graphgraph=newGraph(7); graph.addEdge(1,2,60); graph.addEdge(1,3,10); graph.addEdge(1,5,50); graph.addEdge(2,4,35); graph.addEdge(3,4,30); graph.addEdge(3,5,25); graph.addEdge(4,6,15); graph.addEdge(5,2,30); graph.addEdge(5,6,105); //计算最短距离 graph.dijkstra(1,6); }publicstaticvoidmain(String[]args){
测试结果:
总结
迪杰斯特拉算法的思想与广度优先搜索(BFS)的思路比较像,每次找到自己能到达的顶点,然后依次往外扩散,直到遍历完所有顶点。