文档章节

JAVA实现最短距离算法之迪杰斯特拉算法

一贱书生
 一贱书生
发布于 2017/04/16 20:05
字数 2851
阅读 42
收藏 0

最短路径问题是图论研究中的一个经典的算法问题,旨在寻找图中两个节点之间的最短路径,最常用的算法有Dijkstra算法、SPFA算法\Bellman-Ford算法、Floyd算法\Floyd-Warshall算法、Johnson算法等,这篇博客将重点介绍Dijkstra算法。

 

迪杰斯特拉算法

      迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。具体的计算规则我们可以通过下图进行查看。

img

      通过这幅图(如果图片无法正确显示,请通过百度百科查看)我们可以简单的理解迪杰斯特拉算法算法的基础思路,下面我们就通过Java来实现这个算法。

 

先给出一个无向图

用Dijkstra算法找出以A为起点的单源最短路径步骤如下

 

算法实现

      在具体的实现之前,我们先有一个基础的约定,就是途中的每一个节点我们都用正整数进行编码,相邻两点之间的距离是正整数,图中两个直接相邻两点的距离我们保存到map中,也就是求最短距离我们需要实现这样的一个方法:

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. public MinStep getMinStep(int start, int end, final HashMap<Integer, HashMap<Integer, Integer>> stepLength);  

 

      第一个参数是起始节点的编号,第二个参数是终点节点的编号,第三个参数是图中直接相邻两个节点的距离组成的map。关于第三个参数,会在后面做详细的介绍。这里我们定义一个接口,用于计算两点之间的最短路径,具体如下:

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1.  /**   
  2.  *@Description:      
  3.  */   
  4. package com.lulei.distance;    
  5.   
  6. import java.util.HashMap;  
  7.   
  8. import com.lulei.distance.bean.MinStep;  
  9.     
  10. public interface Distance {  
  11.     public static final MinStep UNREACHABLE = new MinStep(false, -1);  
  12.     /** 
  13.      * @param start 
  14.      * @param end 
  15.      * @param stepLength 
  16.      * @return 
  17.      * @Author:lulei   
  18.      * @Description: 起点到终点的最短路径 
  19.      */  
  20.     public MinStep getMinStep(int start, int end, final HashMap<Integer, HashMap<Integer, Integer>> stepLength);  
  21. }  

 

 

一、方法返回值介绍

      上面方法的返回值是我们自定义的一个数据类型,下面我们通过代码来看其具体的数据结构

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. /**   
  2.  *@Description:      
  3.  */  
  4. package com.lulei.distance.bean;  
  5.   
  6. import java.util.List;  
  7.   
  8. public class MinStep {  
  9.     private boolean reachable;//是否可达  
  10.     private int minStep;//最短步长  
  11.     private List<Integer> step;//最短路径  
  12.   
  13.     public MinStep() {  
  14.     }  
  15.       
  16.     public MinStep(boolean reachable, int minStep) {  
  17.         this.reachable = reachable;  
  18.         this.minStep = minStep;  
  19.     }  
  20.   
  21.     public boolean isReachable() {  
  22.         return reachable;  
  23.     }  
  24.     public void setReachable(boolean reachable) {  
  25.         this.reachable = reachable;  
  26.     }  
  27.     public int getMinStep() {  
  28.         return minStep;  
  29.     }  
  30.     public void setMinStep(int minStep) {  
  31.         this.minStep = minStep;  
  32.     }  
  33.     public List<Integer> getStep() {  
  34.         return step;  
  35.     }  
  36.     public void setStep(List<Integer> step) {  
  37.         this.step = step;  
  38.     }  
  39. }  


      其中最短路径的那个List数组保存了从起点到终点最短路径所经历的节点。

 

 

二、每一个节点的最优前一节点

      在迪杰斯特拉算法中我们需要保存从起点开始到每一个节点最短步长,这也是图中需要比较得出的步长,同时我们还需要存储该步长下的前一个节点是哪个,这样我们就可以通过终点一个一个往前推到起点,这样就出来了完整的最优路径。

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. /**   
  2.  *@Description:      
  3.  */  
  4. package com.lulei.distance.bean;  
  5.   
  6. public class PreNode {  
  7.     private int preNodeNum;// 最优 前一个节点  
  8.     private int nodeStep;// 最小步长  
  9.   
  10.     public PreNode(int preNodeNum, int nodeStep) {  
  11.         this.preNodeNum = preNodeNum;  
  12.         this.nodeStep = nodeStep;  
  13.     }  
  14.   
  15.     public int getPreNodeNum() {  
  16.         return preNodeNum;  
  17.     }  
  18.     public void setPreNodeNum(int preNodeNum) {  
  19.         this.preNodeNum = preNodeNum;  
  20.     }  
  21.     public int getNodeStep() {  
  22.         return nodeStep;  
  23.     }  
  24.     public void setNodeStep(int nodeStep) {  
  25.         this.nodeStep = nodeStep;  
  26.     }  
  27. }  


三、迪杰斯特拉算法计算过程中需要关注的变量

 

      从介绍迪杰斯特拉算法的图中,我们知道在计算的过程中我们需要保存起点到各个节点的最短距离、已经计算过的节点、下次需要计算节点队列和图中相邻两个节点的距离。我们通过代码来看下具体的定义:

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. //key1节点编号,key2节点编号,value为key1到key2的步长  
  2. private HashMap<Integer, HashMap<Integer, Integer>> stepLength;  
  3. //非独立节点个数  
  4. private int nodeNum;  
  5. //移除节点  
  6. private HashSet<Integer> outNode;  
  7. //起点到各点的步长,key为目的节点,value为到目的节点的步长  
  8. private HashMap<Integer, PreNode> nodeStep;  
  9. //下一次计算的节点  
  10. private LinkedList<Integer> nextNode;  
  11. //起点、终点  
  12. private int startNode;  
  13. private int endNode;  

 

      我们这里看下stepLength这个属性,它保存了图中相邻两个节点之间的距离,比如key1=1;key2=3;value=9;这代表的意义就是从节点1到节点3的距离是9。通过这样的存储,我们就需要把图中每两个相邻的点保存到这个类型的map中。

 

四、属性初始化

      在开始计算之前,我们需要对这些属性进行初始化,具体如下:

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. private void initProperty(int start, int end) {  
  2.     outNode = new HashSet<Integer>();  
  3.     nodeStep = new HashMap<Integer, PreNode>();  
  4.     nextNode = new LinkedList<Integer>();  
  5.     nextNode.add(start);  
  6.     startNode = start;  
  7.     endNode = end;  
  8. }  


       这一步我们需要把起点添加到下一次需要计算的节点队列中。

 

 

五、迪杰斯特拉算法

      这一步也就是迪杰斯特拉算法的核心部分,在计算的过程中,我们需要进行如下步骤:

1)判断是否达到终止条件,如果达到终止条件,结束本次算法,如果没有达到,执行下一步;(终止条件:下一次需要计算的节点队列没有数据或已经计算过的节点数等于节点总数)

2)获取下一次计算的节点A;

3)从起点到各节点之间的最短距离map中获取到达A点的最小距离L;

4)获取A节点的可达节点B,计算从起点先到A再到B是否优于已有的其他方式到B,如果优于,则更新B节点,否则不更新;

5)判断B是否是已经移除的节点,如果不是移除的节点,把B添加到下一次需要计算的节点队列中,否则不做操作;

6)判断A节点是否还有除B以外的其他节点,如果有,执行第4)步,否则执行下一步;

7)将A节点从下一次需要计算的节点中移除添加到已经计算过的节点中;

8)执行第一步。

      我们来看下具体的代码实现:

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. private void step() {  
  2.     if (nextNode == null || nextNode.size() < 1) {  
  3.         return;  
  4.     }  
  5.     if (outNode.size() == nodeNum) {  
  6.         return;  
  7.     }  
  8.     //获取下一个计算节点  
  9.     int start = nextNode.removeFirst();  
  10.     //到达该节点的最小距离  
  11.     int step = 0;  
  12.     if (nodeStep.containsKey(start)) {  
  13.         step = nodeStep.get(start).getNodeStep();  
  14.     }  
  15.     //获取该节点可达节点  
  16.     HashMap<Integer,Integer> nextStep = stepLength.get(start);  
  17.     Iterator<Entry<Integer, Integer>> iter = nextStep.entrySet().iterator();  
  18.     while (iter.hasNext()) {  
  19.         Entry<Integer, Integer> entry = iter.next();  
  20.         Integer key = entry.getKey();  
  21.         //如果是起点到起点,不计算之间的步长  
  22.         if (key == startNode) {  
  23.             continue;  
  24.         }  
  25.         //起点到可达节点的距离  
  26.         Integer value = entry.getValue() + step;  
  27.         if ((!nextNode.contains(key)) && (!outNode.contains(key))) {  
  28.             nextNode.add(key);  
  29.         }  
  30.         if (nodeStep.containsKey(key)) {  
  31.             if (value < nodeStep.get(key).getNodeStep()) {  
  32.                 nodeStep.put(key, new PreNode(start, value));  
  33.             }  
  34.         } else {  
  35.             nodeStep.put(key, new PreNode(start, value));  
  36.         }  
  37.     }  
  38.     //将该节点移除  
  39.     outNode.add(start);  
  40.     //计算下一个节点  
  41.     step();  
  42. }  

 

六、组装最短路径返回结果

      通过前面的计算,已经计算出了起点到各个节点的最短路径,下面就需要组装起点到终点的最短路径,在计算最短距离下的路径方式,我们需要从终点依次往前推,即到达终点最短距离下的前一个节点是A,到达A节点最短距离下的前一节点是B,直到找到起点终止。

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. private MinStep changeToMinStep() {  
  2.     MinStep minStep = new MinStep();  
  3.     minStep.setMinStep(nodeStep.get(endNode).getNodeStep());  
  4.     minStep.setReachable(true);  
  5.     LinkedList<Integer> step = new LinkedList<Integer>();  
  6.     minStep.setStep(step);  
  7.     int nodeNum = endNode;  
  8.     step.addFirst(nodeNum);  
  9.     while (nodeStep.containsKey(nodeNum)) {  
  10.         int node = nodeStep.get(nodeNum).getPreNodeNum();  
  11.         step.addFirst(node);  
  12.         nodeNum = node;  
  13.     }  
  14.     return minStep;  
  15. }  


七、接口定义方法实现

 

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. public MinStep getMinStep(int start, int end, final HashMap<Integer, HashMap<Integer, Integer>> stepLength) {  
  2.     this.stepLength = stepLength;  
  3.     this.nodeNum = this.stepLength != null ? this.stepLength.size() : 0;  
  4.     //起点、终点不在目标节点内,返回不可达  
  5.     if (this.stepLength == null || (!this.stepLength.containsKey(start)) || (!this.stepLength.containsKey(end))) {  
  6.         return UNREACHABLE;  
  7.     }  
  8.     initProperty(start, end);  
  9.     step();  
  10.     if (nodeStep.containsKey(end)) {  
  11.         return changeToMinStep();  
  12.     }  
  13.     return UNREACHABLE;  
  14. }  


八、迪杰斯特拉算法完整代码

 

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. /**   
  2.  *@Description:      
  3.  */  
  4. package com.lulei.distance.dijkstra;  
  5.   
  6. import java.util.HashMap;  
  7. import java.util.HashSet;  
  8. import java.util.Iterator;  
  9. import java.util.LinkedList;  
  10. import java.util.Map.Entry;  
  11.   
  12. import com.lulei.distance.Distance;  
  13. import com.lulei.distance.bean.MinStep;  
  14. import com.lulei.distance.bean.PreNode;  
  15.   
  16. public class DistanceDijkstraImpl implements Distance{  
  17.     //key1节点编号,key2节点编号,value为key1到key2的步长  
  18.     private HashMap<Integer, HashMap<Integer, Integer>> stepLength;  
  19.     //非独立节点个数  
  20.     private int nodeNum;  
  21.     //移除节点  
  22.     private HashSet<Integer> outNode;  
  23.     //起点到各点的步长,key为目的节点,value为到目的节点的步长  
  24.     private HashMap<Integer, PreNode> nodeStep;  
  25.     //下一次计算的节点  
  26.     private LinkedList<Integer> nextNode;  
  27.     //起点、终点  
  28.     private int startNode;  
  29.     private int endNode;  
  30.       
  31.     /** 
  32.      * @param start 
  33.      * @param end 
  34.      * @param stepLength 
  35.      * @return 
  36.      * @Author:lulei   
  37.      * @Description: start 到 end 的最短距离 
  38.      */  
  39.     public MinStep getMinStep(int start, int end, final HashMap<Integer, HashMap<Integer, Integer>> stepLength) {  
  40.         this.stepLength = stepLength;  
  41.         this.nodeNum = this.stepLength != null ? this.stepLength.size() : 0;  
  42.         //起点、终点不在目标节点内,返回不可达  
  43.         if (this.stepLength == null || (!this.stepLength.containsKey(start)) || (!this.stepLength.containsKey(end))) {  
  44.             return UNREACHABLE;  
  45.         }  
  46.         initProperty(start, end);  
  47.         step();  
  48.         if (nodeStep.containsKey(end)) {  
  49.             return changeToMinStep();  
  50.         }  
  51.         return UNREACHABLE;  
  52.     }  
  53.       
  54.     /** 
  55.      * 返回最短距离以及路径 
  56.      */  
  57.     private MinStep changeToMinStep() {  
  58.         MinStep minStep = new MinStep();  
  59.         minStep.setMinStep(nodeStep.get(endNode).getNodeStep());  
  60.         minStep.setReachable(true);  
  61.         LinkedList<Integer> step = new LinkedList<Integer>();  
  62.         minStep.setStep(step);  
  63.         int nodeNum = endNode;  
  64.         step.addFirst(nodeNum);  
  65.         while (nodeStep.containsKey(nodeNum)) {  
  66.             int node = nodeStep.get(nodeNum).getPreNodeNum();  
  67.             step.addFirst(node);  
  68.             nodeNum = node;  
  69.         }  
  70.         return minStep;  
  71.     }  
  72.       
  73.     /** 
  74.      * @param start 
  75.      * @Author:lulei   
  76.      * @Description: 初始化属性 
  77.      */  
  78.     private void initProperty(int start, int end) {  
  79.         outNode = new HashSet<Integer>();  
  80.         nodeStep = new HashMap<Integer, PreNode>();  
  81.         nextNode = new LinkedList<Integer>();  
  82.         nextNode.add(start);  
  83.         startNode = start;  
  84.         endNode = end;  
  85.     }  
  86.       
  87.     /** 
  88.      * @param end 
  89.      * @Author:lulei   
  90.      * @Description: 
  91.      */  
  92.     private void step() {  
  93.         if (nextNode == null || nextNode.size() < 1) {  
  94.             return;  
  95.         }  
  96.         if (outNode.size() == nodeNum) {  
  97.             return;  
  98.         }  
  99.         //获取下一个计算节点  
  100.         int start = nextNode.removeFirst();  
  101.         //到达该节点的最小距离  
  102.         int step = 0;  
  103.         if (nodeStep.containsKey(start)) {  
  104.             step = nodeStep.get(start).getNodeStep();  
  105.         }  
  106.         //获取该节点可达节点  
  107.         HashMap<Integer,Integer> nextStep = stepLength.get(start);  
  108.         Iterator<Entry<Integer, Integer>> iter = nextStep.entrySet().iterator();  
  109.         while (iter.hasNext()) {  
  110.             Entry<Integer, Integer> entry = iter.next();  
  111.             Integer key = entry.getKey();  
  112.             //如果是起点到起点,不计算之间的步长  
  113.             if (key == startNode) {  
  114.                 continue;  
  115.             }  
  116.             //起点到可达节点的距离  
  117.             Integer value = entry.getValue() + step;  
  118.             if ((!nextNode.contains(key)) && (!outNode.contains(key))) {  
  119.                 nextNode.add(key);  
  120.             }  
  121.             if (nodeStep.containsKey(key)) {  
  122.                 if (value < nodeStep.get(key).getNodeStep()) {  
  123.                     nodeStep.put(key, new PreNode(start, value));  
  124.                 }  
  125.             } else {  
  126.                 nodeStep.put(key, new PreNode(start, value));  
  127.             }  
  128.         }  
  129.         //将该节点移除  
  130.         outNode.add(start);  
  131.         //计算下一个节点  
  132.         step();  
  133.     }  
  134. }  


 

 

代码测试

     对于上述代码的测试,我们还是使用我们事例图形中的例子,计算从节点1到节点5的最短距离。

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1.  /**   
  2.  *@Description:      
  3.  */   
  4. package com.lulei.distance.test;    
  5.   
  6. import java.util.HashMap;  
  7.   
  8. import com.lulei.distance.Distance;  
  9. import com.lulei.distance.bean.MinStep;  
  10. import com.lulei.distance.dijkstra.DistanceDijkstraImpl;  
  11. import com.lulei.util.JsonUtil;  
  12.     
  13. public class DistanceTest {  
  14.   
  15.     public static void main(String[] args) {  
  16.         // TODO Auto-generated method stub    
  17.         HashMap<Integer, HashMap<Integer,Integer>> stepLength = new HashMap<Integer, HashMap<Integer,Integer>>();  
  18.         HashMap<Integer,Integer> step1 = new HashMap<Integer, Integer>();  
  19.         stepLength.put(1, step1);  
  20.         step1.put(6, 14);  
  21.         step1.put(3, 9);  
  22.         step1.put(2, 7);  
  23.           
  24.         HashMap<Integer,Integer> step2 = new HashMap<Integer, Integer>();  
  25.         stepLength.put(2, step2);  
  26.         step2.put(1, 7);  
  27.         step2.put(3, 10);  
  28.         step2.put(4, 15);  
  29.           
  30.         HashMap<Integer,Integer> step3 = new HashMap<Integer, Integer>();  
  31.         stepLength.put(3, step3);  
  32.         step3.put(1, 9);  
  33.         step3.put(2, 10);  
  34.         step3.put(4, 11);  
  35.         step3.put(6, 2);  
  36.           
  37.         HashMap<Integer,Integer> step4 = new HashMap<Integer, Integer>();  
  38.         stepLength.put(4, step4);  
  39.         step4.put(2, 15);  
  40.         step4.put(5, 5);  
  41.         step4.put(3, 11);  
  42.           
  43.         HashMap<Integer,Integer> step5 = new HashMap<Integer, Integer>();  
  44.         stepLength.put(5, step5);  
  45.         step5.put(6, 9);  
  46.         step5.put(4, 5);  
  47.           
  48.         HashMap<Integer,Integer> step6 = new HashMap<Integer, Integer>();  
  49.         stepLength.put(6, step6);  
  50.         step6.put(1, 14);  
  51.         step6.put(5, 9);  
  52.         step6.put(3, 2);  
  53.           
  54.         Distance distance = new DistanceDijkstraImpl();  
  55.         MinStep step = distance.getMinStep(1, 5, stepLength);  
  56.         System.out.println(JsonUtil.parseJson(step));  
  57.     }  
  58.   
  59. }  


      这里组装相邻两个节点之间的距离用了大量的代码,我们看下输出结果:

 

 

[java] view plain copy

 print?在CODE上查看代码片派生到我的代码片

  1. {"reachable":true,"minStep":20,"step":[1,3,6,5]}  


 

 

最后的思考

      最短路径算法在现实生活中其实有很多的用处,比如迷宫解法、路径规划、路由寻址等等,这些问题看似很复杂,其实只需要做对应的转化后还是可以用最基础的算法解决的。

本文转载自:http://blog.csdn.net/xiaojimanman/article/details/50889670

上一篇: 贪心算法
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
Dijkstra算法之 Java详解

迪杰斯特拉算法介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为...

孟飞阳
03/26
0
0
基本算法——图算法之最短路径(Dijkstra)

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,针对的是非负权边,解决的是有向图中最短路径问题。迪杰...

安然若知
2018/07/13
0
0
迪杰斯特拉(Dijkstra)算法描述与路径计算

1.迪杰斯特拉算法描述 迪杰斯特拉算法是基于LLDP(一种由IEEE802.1AB[11]定义的链路层发现协议)获取信息,是一个从顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特...

墨痕hz
2017/11/28
0
0
游戏中的人工智能之流场寻路

流场简介 流场,一般为网格图,网格中的每一个节点包含一个向量,该向量是物体在该位置时期望的速度。 流场寻路 利用流场的速度信息指导大量物体同时进行寻路。换句话说,如何生成可以寻路的...

RonTang
2016/04/20
0
0
java实现Dijkstra算法求最短路径

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra一般的表述通常有两...

zaizai_loong
2013/09/08
0
2

没有更多内容

加载失败,请刷新页面

加载更多

Java agentlib参数分析

Java agentlib参数分析 再用intellij idea进行远程调试的时候,具体的配置选项如下: 标红的一行显示了远程调试需要添加的虚拟机参数。这个参数到底有什么意义? 我在命令行输入java命令,输...

Mr_Tea伯奕
34分钟前
1
0
四种软件架构演进史,程序员会一种就很牛了!

如果一个软件开发人员,不了解软件架构的演进,会制约技术的选型和开发人员的生存、晋升空间。这里我列举了目前主要的四种软件架构以及他们的优缺点,希望能够帮助软件开发人员拓展知识面。 ...

我最喜欢三大框架
38分钟前
3
0
如何做高可用的架构设计?

定义目标 既然我们的目标是做到高可用,那么我们就有必要先明确清楚高可用的含义,并通过拆解目标,让目标可以被量化。按照我的理解,可以将目标按照以下三条进行拆解: 1. 保持业务高稳定性...

别打我会飞
39分钟前
2
0
《错误的行为》的读后感优秀范文4000字

《错误的行为》的读后感优秀范文4000字: 第一章经济人和非理性人。本书中的经纪人是指经济学家经济模式中虚拟的理想人物,非理性人是指现实生活中实实在在存在的人,与经济人相对应的人。 ...

原创小博客
50分钟前
3
0
将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向

作者图解释很好 https://blog.csdn.net/yanxiaolx/article/details/52073221

南桥北木
55分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部