乐虎游戏|乐虎国际登录|欢迎你

Dijkstra算法(一)之 C语言详解

日期:2019-11-04编辑作者:计算机资讯

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

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

迪杰斯特拉算法

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

图片 1

通过这幅图我们可以简单的理解迪杰斯特拉算法算法的基础思路,下面我们就通过JAVA来实现这个算法。

算法实现

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

public MinStep getMinStep(int start, int end, final HashMap> stepLength);

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

 /**  
 [email protected]:     
 */ 
package com.lulei.distance;  

import java.util.HashMap;

import com.lulei.distance.bean.MinStep;

public interface Distance {
 public static final MinStep UNREACHABLE = new MinStep(false, -1);
 /**
  * @param start
  * @param end
  * @param stepLength
  * @return
  * @Author:lulei  
  * @Description: 起点到终点的最短路径
  */
 public MinStep getMinStep(int start, int end, final HashMap> stepLength);
}

一、方法返回值介绍

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

/**  
 [email protected]:     
 */
package com.lulei.distance.bean;

import java.util.List;

public class MinStep {
 private boolean reachable;//是否可达
 private int minStep;//最短步长
 private List step;//最短路径

 public MinStep() {
 }

 public MinStep(boolean reachable, int minStep) {
  this.reachable = reachable;
  this.minStep = minStep;
 }

 public boolean isReachable() {
  return reachable;
 }
 public void setReachable(boolean reachable) {
  this.reachable = reachable;
 }
 public int getMinStep() {
  return minStep;
 }
 public void setMinStep(int minStep) {
  this.minStep = minStep;
 }
 public List getStep() {
  return step;
 }
 public void setStep(List step) {
  this.step = step;
 }
}

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

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

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

/**  
 [email protected]:     
 */
package com.lulei.distance.bean;

public class PreNode {
 private int preNodeNum;// 最优 前一个节点
 private int nodeStep;// 最小步长

 public PreNode(int preNodeNum, int nodeStep) {
  this.preNodeNum = preNodeNum;
  this.nodeStep = nodeStep;
 }

 public int getPreNodeNum() {
  return preNodeNum;
 }
 public void setPreNodeNum(int preNodeNum) {
  this.preNodeNum = preNodeNum;
 }
 public int getNodeStep() {
  return nodeStep;
 }
 public void setNodeStep(int nodeStep) {
  this.nodeStep = nodeStep;
 }
}

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

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

//key1节点编号,key2节点编号,value为key1到key2的步长
private HashMap> stepLength;
//非独立节点个数
private int nodeNum;
//移除节点
private HashSet outNode;
//起点到各点的步长,key为目的节点,value为到目的节点的步长
private HashMap nodeStep;
//下一次计算的节点
private LinkedList nextNode;
//起点、终点
private int startNode;
private int endNode;

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

四、属性初始化

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

private void initProperty(int start, int end) {
 outNode = new HashSet();
 nodeStep = new HashMap();
 nextNode = new LinkedList();
 nextNode.add(start);
 startNode = start;
 endNode = end;
}

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

五、迪杰斯特拉算法

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

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

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

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

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

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

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

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

8)执行第一步。

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

private void step() {
 if (nextNode == null || nextNode.size() < 1) {
  return;
 }
 if (outNode.size() == nodeNum) {
  return;
 }
 //获取下一个计算节点
 int start = nextNode.removeFirst();
 //到达该节点的最小距离
 int step = 0;
 if (nodeStep.containsKey(start)) {
  step = nodeStep.get(start).getNodeStep();
 }
 //获取该节点可达节点
 HashMap nextStep = stepLength.get(start);
 Iterator> iter = nextStep.entrySet().iterator();
 while (iter.hasNext()) {
  Entry entry = iter.next();
  Integer key = entry.getKey();
  //如果是起点到起点,不计算之间的步长
  if (key == startNode) {
   continue;
  }
  //起点到可达节点的距离
  Integer value = entry.getValue() + step;
  if ((!nextNode.contains(key)) && (!outNode.contains(key))) {
   nextNode.add(key);
  }
  if (nodeStep.containsKey(key)) {
   if (value < nodeStep.get(key).getNodeStep()) {
    nodeStep.put(key, new PreNode(start, value));
   }
  } else {
   nodeStep.put(key, new PreNode(start, value));
  }
 }
 //将该节点移除
 outNode.add(start);
 //计算下一个节点
 step();
}

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

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

private MinStep changeToMinStep() {
 MinStep minStep = new MinStep();
 minStep.setMinStep(nodeStep.get(endNode).getNodeStep());
 minStep.setReachable(true);
 LinkedList step = new LinkedList();
 minStep.setStep(step);
 int nodeNum = endNode;
 step.addFirst(nodeNum);
 while (nodeStep.containsKey(nodeNum)) {
  int node = nodeStep.get(nodeNum).getPreNodeNum();
  step.addFirst(node);
  nodeNum = node;
 }
 return minStep;
}

七、接口定义方法实现

public MinStep getMinStep(int start, int end, final HashMap> stepLength) {
 this.stepLength = stepLength;
 this.nodeNum = this.stepLength != null ? this.stepLength.size() : 0;
 //起点、终点不在目标节点内,返回不可达
 if (this.stepLength == null || (!this.stepLength.containsKey(start)) || (!this.stepLength.containsKey(end))) {
  return UNREACHABLE;
 }
 initProperty(start, end);
 step();
 if (nodeStep.containsKey(end)) {
  return changeToMinStep();
 }
 return UNREACHABLE;
}

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

 

 

/**  
 [email protected]:     
 */
package com.lulei.distance.dijkstra;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

import com.lulei.distance.Distance;
import com.lulei.distance.bean.MinStep;
import com.lulei.distance.bean.PreNode;

public class DistanceDijkstraImpl implements Distance{
 //key1节点编号,key2节点编号,value为key1到key2的步长
 private HashMap> stepLength;
 //非独立节点个数
 private int nodeNum;
 //移除节点
 private HashSet outNode;
 //起点到各点的步长,key为目的节点,value为到目的节点的步长
 private HashMap nodeStep;
 //下一次计算的节点
 private LinkedList nextNode;
 //起点、终点
 private int startNode;
 private int endNode;

 /**
  * @param start
  * @param end
  * @param stepLength
  * @return
  * @Author:lulei  
  * @Description: start 到 end 的最短距离
  */
 public MinStep getMinStep(int start, int end, final HashMap> stepLength) {
  this.stepLength = stepLength;
  this.nodeNum = this.stepLength != null ? this.stepLength.size() : 0;
  //起点、终点不在目标节点内,返回不可达
  if (this.stepLength == null || (!this.stepLength.containsKey(start)) || (!this.stepLength.containsKey(end))) {
   return UNREACHABLE;
  }
  initProperty(start, end);
  step();
  if (nodeStep.containsKey(end)) {
   return changeToMinStep();
  }
  return UNREACHABLE;
 }

 /**
  * 返回最短距离以及路径
  */
 private MinStep changeToMinStep() {
  MinStep minStep = new MinStep();
  minStep.setMinStep(nodeStep.get(endNode).getNodeStep());
  minStep.setReachable(true);
  LinkedList step = new LinkedList();
  minStep.setStep(step);
  int nodeNum = endNode;
  step.addFirst(nodeNum);
  while (nodeStep.containsKey(nodeNum)) {
   int node = nodeStep.get(nodeNum).getPreNodeNum();
   step.addFirst(node);
   nodeNum = node;
  }
  return minStep;
 }

 /**
  * @param start
  * @Author:lulei  
  * @Description: 初始化属性
  */
 private void initProperty(int start, int end) {
  outNode = new HashSet();
  nodeStep = new HashMap();
  nextNode = new LinkedList();
  nextNode.add(start);
  startNode = start;
  endNode = end;
 }

 /**
  * @param end
  * @Author:lulei  
  * @Description:
  */
 private void step() {
  if (nextNode == null || nextNode.size() < 1) {
   return;
  }
  if (outNode.size() == nodeNum) {
   return;
  }
  //获取下一个计算节点
  int start = nextNode.removeFirst();
  //到达该节点的最小距离
  int step = 0;
  if (nodeStep.containsKey(start)) {
   step = nodeStep.get(start).getNodeStep();
  }
  //获取该节点可达节点
  HashMap nextStep = stepLength.get(start);
  Iterator> iter = nextStep.entrySet().iterator();
  while (iter.hasNext()) {
   Entry entry = iter.next();
   Integer key = entry.getKey();
   //如果是起点到起点,不计算之间的步长
   if (key == startNode) {
    continue;
   }
   //起点到可达节点的距离
   Integer value = entry.getValue() + step;
   if ((!nextNode.contains(key)) && (!outNode.contains(key))) {
    nextNode.add(key);
   }
   if (nodeStep.containsKey(key)) {
    if (value < nodeStep.get(key).getNodeStep()) {
     nodeStep.put(key, new PreNode(start, value));
    }
   } else {
    nodeStep.put(key, new PreNode(start, value));
   }
  }
  //将该节点移除
  outNode.add(start);
  //计算下一个节点
  step();
 }
}

代码测试

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

 

 /**  
 [email protected]:     
 */ 
package com.lulei.distance.test;  

import java.util.HashMap;

import com.lulei.distance.Distance;
import com.lulei.distance.bean.MinStep;
import com.lulei.distance.dijkstra.DistanceDijkstraImpl;
import com.lulei.util.JsonUtil;

public class DistanceTest {

 public static void main(String[] args) {
  // TODO Auto-generated method stub  
  HashMap> stepLength = new HashMap>();
  HashMap step1 = new HashMap();
  stepLength.put(1, step1);
  step1.put(6, 14);
  step1.put(3, 9);
  step1.put(2, 7);

  HashMap step2 = new HashMap();
  stepLength.put(2, step2);
  step2.put(1, 7);
  step2.put(3, 10);
  step2.put(4, 15);

  HashMap step3 = new HashMap();
  stepLength.put(3, step3);
  step3.put(1, 9);
  step3.put(2, 10);
  step3.put(4, 11);
  step3.put(6, 2);

  HashMap step4 = new HashMap();
  stepLength.put(4, step4);
  step4.put(2, 15);
  step4.put(5, 5);
  step4.put(3, 11);

  HashMap step5 = new HashMap();
  stepLength.put(5, step5);
  step5.put(6, 9);
  step5.put(4, 5);

  HashMap step6 = new HashMap();
  stepLength.put(6, step6);
  step6.put(1, 14);
  step6.put(5, 9);
  step6.put(3, 2);

  Distance distance = new DistanceDijkstraImpl();
  MinStep step = distance.getMinStep(1, 5, stepLength);
  System.out.println(JsonUtil.parseJson(step));
 }

}

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

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

最后的思考

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

最近发现很多网站或者个人转载博客,个人拒绝他人转载,但是最起码你给出我文章的出处,不会让我认为自己辛辛苦苦写的博客被别人剽窃。说到转载问题,又需要提到现在的互联网环境,有时候自己去找一篇博客,发现很难找到源作者或者最初的链接,一方面,自己写博客不想在博文中添加自己的博客地址介绍影响博文的质量,另一方面博主有的时候对博文中的错误进行了修改,他人无法快速获取该信息。

最短路径问题是图论研究中的一个经典的算法问题,旨在寻找图中两个节点之间的最短路径,最常...

Hello,朋友们。第二篇博客我们还是接着聊运动规划算法。

本章介绍迪杰斯特拉算法。和以往一样,本文会先对迪杰斯特拉算法的理论论知识进行介绍,然后给出C语言的实现。后续再分别给出C++和Java版本的实现。

目录
1. 迪杰斯特拉算法介绍
2. 迪杰斯特拉算法图解
3. 迪杰斯特拉算法的代码说明
4. 迪杰斯特拉算法的源码

转载请注明出处:

更多内容:数据结构与算法系列 目录

上图,图中字母表示不同的地点,数字表示两点之间的距离。我们要找到图中的最短路径,就拿AE点做例子好了。

迪杰斯特拉算法介绍

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

基本思想

     通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算)。

     此外,引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

     初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是"起点s到该顶点的路径"。然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 ... 重复该操作,直到遍历完所有顶点。

操作步骤

(1) 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。

(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。

(4) 重复步骤(2)和(3),直到遍历完所有顶点。

单纯的看上面的理论可能比较难以理解,下面通过实例来对该算法进行说明。

图片 2

迪杰斯特拉算法图解

图片 3

以上图G4为例,来对迪杰斯特拉进行算法演示(以第4个顶点D为起点)。

图片 4

初始状态:S是已计算出最短路径的顶点集合,U是未计算除最短路径的顶点的集合!
第1步:将顶点D加入到S中。
    此时,S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。     注:C(3)表示C到起点D的距离是3。

第2步:将顶点C加入到S中。
    上一步操作之后,U中顶点C到起点D的距离最短;因此,将C加入到S中,同时更新U中顶点的距离。以顶点F为例,之前F到D的距离为∞;但是将C加入到S之后,F到D的距离为9=(F,C)+(C,D)。
    此时,S={D(0),C(3)}, U={A(∞),B(23),E(4),F(9),G(∞)}。

第3步:将顶点E加入到S中。
    上一步操作之后,U中顶点E到起点D的距离最短;因此,将E加入到S中,同时更新U中顶点的距离。还是以顶点F为例,之前F到D的距离为9;但是将E加入到S之后,F到D的距离为6=(F,E)+(E,D)。
    此时,S={D(0),C(3),E(4)}, U={A(∞),B(23),F(6),G(12)}。

第4步:将顶点F加入到S中。
    此时,S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。

第5步:将顶点G加入到S中。
    此时,S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。

第6步:将顶点B加入到S中。
    此时,S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。

第7步:将顶点A加入到S中。
    此时,S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。

此时,起点D到各个顶点的最短距离就计算出来了:A(22) B(13) C(3) D(0) E(4) F(6) G(12)

图1

迪杰斯特拉算法的代码说明

以"邻接矩阵"为例对迪杰斯特拉算法进行说明,对于"邻接表"实现的图在后面会给出相应的源码。

1. 基本定义

// 邻接矩阵  typedef struct _graph  {      char vexs[MAX];       // 顶点集合      int vexnum;           // 顶点数      int edgnum;           // 边数      int matrix[MAX][MAX]; // 邻接矩阵  }Graph, *PGraph;    // 边的结构体  typedef struct _EdgeData  {      char start; // 边的起点      char end;   // 边的终点      int weight; // 边的权重  }EData;  

Graph是邻接矩阵对应的结构体。
vexs用于保存顶点,vexnum是顶点数,edgnum是边数;matrix则是用于保存矩阵信息的二维数组。例如,matrix[i][j]=1,则表示"顶点i(即vexs[i])"和"顶点j(即vexs[j])"是邻接点;matrix[i][j]=0,则表示它们不是邻接点。
EData是邻接矩阵边对应的结构体。

2. 迪杰斯特拉算法

/*   * Dijkstra最短路径。   * 即,统计图(G)中"顶点vs"到其它各个顶点的最短路径。   *   * 参数说明:   *        G -- 图   *       vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。   *     prev -- 前驱顶点数组。即,prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中,位于"顶点i"之前的那个顶点。   *     dist -- 长度数组。即,dist[i]是"顶点vs"到"顶点i"的最短路径的长度。   */  void dijkstra(Graph G, int vs, int prev[], int dist[])  {      int i,j,k;      int min;      int tmp;      int flag[MAX];      // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。        // 初始化      for (i = 0; i < G.vexnum; i++)      {          flag[i] = 0;              // 顶点i的最短路径还没获取到。          prev[i] = 0;              // 顶点i的前驱顶点为0。          dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。      }        // 对"顶点vs"自身进行初始化      flag[vs] = 1;      dist[vs] = 0;        // 遍历G.vexnum-1次;每次找出一个顶点的最短路径。      for (i = 1; i < G.vexnum; i++)      {          // 寻找当前最小的路径;          // 即,在未获取最短路径的顶点中,找到离vs最近的顶点(k)。          min = INF;          for (j = 0; j < G.vexnum; j++)          {              if (flag[j]==0 && dist[j]<min)              {                  min = dist[j];                  k = j;              }          }          // 标记"顶点k"为已经获取到最短路径          flag[k] = 1;            // 修正当前最短路径和前驱顶点          // 即,当已经"顶点k的最短路径"之后,更新"未获取最短路径的顶点的最短路径和前驱顶点"。          for (j = 0; j < G.vexnum; j++)          {              tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出              if (flag[j] == 0 && (tmp  < dist[j]) )              {                  dist[j] = tmp;                  prev[j] = k;              }          }      }        // 打印dijkstra最短路径的结果      printf("dijkstra(%c): n", G.vexs[vs]);      for (i = 0; i < G.vexnum; i++)          printf("  shortest(%c, %c)=%dn", G.vexs[vs], G.vexs[i], dist[i]);  }  

我们的目标是:找到start-end之间的最短路径,如图所示

迪杰斯特拉算法的源码

这里分别给出"邻接矩阵图"和"邻接表图"的迪杰斯特拉算法源码。

1. 邻接矩阵源码(matrix_udg.c)

2. 邻接表源码(list_udg.c)


图片 5

图2

来吧,Dijkstra-迪杰斯特拉算法,这是一种基于贪心策略的动态规划算法(后面解释这句话),可以用来解决最短路径问题。

首先把起点的距离设定为0(A到A当然是0距离拉),然后把已经确认该点到起点之间的距离为最短距离的点标红(血统清晰)

图片 6

图3

下一步,我们考虑和A相邻的点B,D, F ,把这些候选者们标蓝(血统不明)

图片 7

图4

本文由乐虎游戏发布于计算机资讯,转载请注明出处:Dijkstra算法(一)之 C语言详解

关键词:

Selenium WebDriver的使用(一),seleniumwebdriver

Selenium WebDriver的使用(一),seleniumwebdriver Selenium WebDriver的有关介绍及能源下载: 在二零一四年5月份SeleniumWebDriver更...

详细>>

Shiro权限认证

Shiro权限认证 ApacheShiro是三个强有力而灵活的开源安全框架(本来想传到网盘供我们下载,不过出于本国网盘动不动将...

详细>>

203. Remove Linked List Elements,linkedelements

203. Remove Linked List Elements,linkedelements Remove all elements from a linked list of integers that havevalue  val . Example Given:  1 -- 2 -- ...

详细>>

汤姆cat配置虚构主机

Tomcat 设置二级域名 一、打开tomcat安装目录下conf/server.xml这个文件         在server.xml文档中找到 /Engine /Service 接着...

详细>>