首页 > java教程 > 正文

Java中关于最短路径算法之Dijkstra算法的实现

原创 2017-10-13 10:29:18 0 278
这篇文章主要介绍了java实现最短路径算法之Dijkstra算法, Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法,有兴趣的可以了解一下

前言

Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法。该算法被称为是“贪心算法”的成功典范。本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码。

一、知识准备:

1、表示图的数据结构

用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵。

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。

设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:

从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。

从这个矩阵中,很容易知道图中的信息。

(1)要判断任意两顶点是否有边无边就很容易了;

(2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;

(3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;

而有向图讲究入度和出度,顶点vi的入度为1,正好是第i列各数之和。顶点vi的出度为2,即第i行的各数之和。

有向图的定义也类似,故不做赘述。

2、单起点全路径

所谓单起点全路径,就是指在一个图中,从一个起点出发,到所有节点的最短路径。

3、图论的基本知识(读者需自行寻找相关资料)

4、互补松弛条件

设标量d1,d2,....,dN满足

dj<=di + aij, (i,j)属于A,

且P是以i1为起点ik为终点的路,如果

dj = di + aij, 对P的所有边(i, j)

成立,那么P是从i1到ik的最短路。其中,满足上面两式的被称为最短路问题的互补松弛条件。

二、算法思想

1、令G = (V,E)为一个带权无向图。G中若有两个相邻的节点,i和j。aij(在这及其后面都表示为下标,请注意)为节点i到节点j的权值,在本算法可以理解为距离。每个节点都有一个值di(节点标记)表示其从起点到它的某条路的距离。

2、算法初始有一个数组V用于储存未访问节点的列表,我们暂称为候选列表。选定节点1为起始节点。开始时,节点1的d1=0, 其他节点di=无穷大,V为所有节点。
初始化条件后,然后开始迭代算法,直到V为空集时停止。具体迭代步骤如下:

将d值最小的节点di从候选列表中移除。(本例中V的数据结构采用的是优先队列实现最小值出列,最好使用斐波那契对,在以前文章有过介绍,性能有大幅提示)。对于以该节点为起点的每一条边,不包括移除V的节点, (i, j)属于A, 若dj > di + aij(违反松弛条件),则令

dj = di + aij , (如果j已经从V中移除过,说明其最小距离已经计算出,不参与此次计算)

可以看到在算法的运算工程中,节点的d值是单调不增的

具体算法图解如下

  

三、java代码实现


public class Vertex implements Comparable<Vertex>{

  /**
   * 节点名称(A,B,C,D)
   */
  private String name;
  
  /**
   * 最短路径长度
   */
  private int path;
  
  /**
   * 节点是否已经出列(是否已经处理完毕)
   */
  private boolean isMarked;
  
  public Vertex(String name){
    this.name = name;
    this.path = Integer.MAX_VALUE; //初始设置为无穷大
    this.setMarked(false);
  }
  
  public Vertex(String name, int path){
    this.name = name;
    this.path = path;
    this.setMarked(false);
  }
  
  @Override
  public int compareTo(Vertex o) {
    return o.path > path?-1:1;
  }
}


public class Graph {

  /*
   * 顶点
   */
  private List<Vertex> vertexs;

  /*
   * 边
   */
  private int[][] edges;

  /*
   * 没有访问的顶点
   */
  private Queue<Vertex> unVisited;

  public Graph(List<Vertex> vertexs, int[][] edges) {
    this.vertexs = vertexs;
    this.edges = edges;
    initUnVisited();
  }
  
  /*
   * 搜索各顶点最短路径
   */
  public void search(){
    while(!unVisited.isEmpty()){
      Vertex vertex = unVisited.element();
      //顶点已经计算出最短路径,设置为"已访问"
       vertex.setMarked(true);  
      //获取所有"未访问"的邻居
        List<Vertex> neighbors = getNeighbors(vertex);  
      //更新邻居的最短路径
      updatesDistance(vertex, neighbors);    
      pop();
    }
    System.out.println("search over");
  }
  
  /*
   * 更新所有邻居的最短路径
   */
  private void updatesDistance(Vertex vertex, List<Vertex> neighbors){
    for(Vertex neighbor: neighbors){
      updateDistance(vertex, neighbor);
    }
  }
  
  /*
   * 更新邻居的最短路径
   */
  private void updateDistance(Vertex vertex, Vertex neighbor){
    int distance = getDistance(vertex, neighbor) + vertex.getPath();
    if(distance < neighbor.getPath()){
      neighbor.setPath(distance);
    }
  }

  /*
   * 初始化未访问顶点集合
   */
  private void initUnVisited() {
    unVisited = new PriorityQueue<Vertex>();
    for (Vertex v : vertexs) {
      unVisited.add(v);
    }
  }

  /*
   * 从未访问顶点集合中删除已找到最短路径的节点
   */
  private void pop() {
    unVisited.poll();
  }

  /*
   * 获取顶点到目标顶点的距离
   */
  private int getDistance(Vertex source, Vertex destination) {
    int sourceIndex = vertexs.indexOf(source);
    int destIndex = vertexs.indexOf(destination);
    return edges[sourceIndex][destIndex];
  }

  /*
   * 获取顶点所有(未访问的)邻居
   */
  private List<Vertex> getNeighbors(Vertex v) {
    List<Vertex> neighbors = new ArrayList<Vertex>();
    int position = vertexs.indexOf(v);
    Vertex neighbor = null;
    int distance;
    for (int i = 0; i < vertexs.size(); i++) {
      if (i == position) {
        //顶点本身,跳过
        continue;
      }
      distance = edges[position][i];  //到所有顶点的距离
      if (distance < Integer.MAX_VALUE) {
        //是邻居(有路径可达)
        neighbor = getVertex(i);
        if (!neighbor.isMarked()) {
          //如果邻居没有访问过,则加入list;
          neighbors.add(neighbor);
        }
      }
    }
    return neighbors;
  }

  /*
   * 根据顶点位置获取顶点
   */
  private Vertex getVertex(int index) {
    return vertexs.get(index);
  }

  /*
   * 打印图
   */
  public void printGraph() {
    int verNums = vertexs.size();
    for (int row = 0; row < verNums; row++) {
      for (int col = 0; col < verNums; col++) {
        if(Integer.MAX_VALUE == edges[row][col]){
          System.out.print("X");
          System.out.print(" ");
          continue;
        }
        System.out.print(edges[row][col]);
        System.out.print(" ");
      }
      System.out.println();
    }
  }
}


public class Test {

  public static void main(String[] args){
    List<Vertex> vertexs = new ArrayList<Vertex>();
    Vertex a = new Vertex("A", 0);
    Vertex b = new Vertex("B");
    Vertex c = new Vertex("C");
    Vertex d = new Vertex("D");
    Vertex e = new Vertex("E");
    Vertex f = new Vertex("F");
    vertexs.add(a);
    vertexs.add(b);
    vertexs.add(c);
    vertexs.add(d);
    vertexs.add(e);
    vertexs.add(f);
    int[][] edges = {
        {Integer.MAX_VALUE,6,3,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
        {6,Integer.MAX_VALUE,2,5,Integer.MAX_VALUE,Integer.MAX_VALUE},
        {3,2,Integer.MAX_VALUE,3,4,Integer.MAX_VALUE},
        {Integer.MAX_VALUE,5,3,Integer.MAX_VALUE,5,3},
        {Integer.MAX_VALUE,Integer.MAX_VALUE,4,5,Integer.MAX_VALUE,5},
        {Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,3,5,Integer.MAX_VALUE}
    
    };
    Graph graph = new Graph(vertexs, edges);
    graph.printGraph();
    graph.search();
  }
  
}

以上就是Java中关于最短路径算法之Dijkstra算法的实现的详细内容,更多请关注php中文网其它相关文章!

  • 相关标签:java 算法 路径
  • 本文原创发布php中文网 ,转载请注明出处,感谢您的尊重!
  • 网友评论

    文明上网理性发言,请遵守 新闻评论服务协议

    条评论

    独孤九贱(4)_PHP视频教程

    江湖传言:PHP是世界上最好的编程语言。真的是这样吗?这个梗究竟是从哪来的?学会本课程,你就会明白了。 PHP中文网出品的PHP入门系统教学视频,完全从初学者的角度出发,绝不玩虚的,一切以实用、有用...

    独孤九贱(5)_ThinkPHP5视频教程

    ThinkPHP是国内最流行的中文PHP开发框架,也是您Web项目的最佳选择。《php.cn独孤九贱(5)-ThinkPHP5视频教程》课程以ThinkPHP5最新版本为例,从最基本的框架常识开始,将...

    ThinkPHP5实战之[教学管理系统]

    本套教程,以一个真实的学校教学管理系统为案例,手把手教会您如何在一张白纸上,从零开始,一步一步的用ThinkPHP5框架快速开发出一个商业项目。

    独孤九贱(1)_HTML5视频教程

    《php.cn原创html5视频教程》课程特色:php中文网原创幽默段子系列课程,以恶搞,段子为主题风格的php视频教程!轻松的教学风格,简短的教学模式,让同学们在不知不觉中,学会了HTML知识。 ...

    PHP入门视频教程之一周学会PHP

    所有计算机语言的学习都要从基础开始,《PHP入门视频教程之一周学会PHP》不仅是PHP的基础部分更主要的是PHP语言的核心技术,是学习PHP必须掌握的内容,任何PHP项目的实现都离不开这部分的内容,通...

    ThinkPHP5快速开发企业站点[全程实录]更新中...

    本课以最新版ThinkPHP5.0.10为基础进行开发,全程实录一个完整企业点,从后台到前台,从控制器到路由的全套完整教程,不论是你是新人,还是有一定开发经验的程序员,都可以从中学到实用的知识~~

    Thinkphp3.2.3个人博客开发

    ThinkPHP是一个快速、开源的轻量级国产PHP开发框架,是业内最流行的PHP框架之一。本课程以博客系统为例,讲述如何使用TP实战开发,从中学习Thinkphp的实践应用。模版下载地址:http:/...

    PHP实战天龙八部之仿爱奇艺电影网站

    本课程是php实战开发课程,以爱奇艺电影网站为蓝本从零开发一个自己的网站。目的是让大家了解真实项目的架构及开发过程

    独孤九贱(8)_php从零开始开发属于自己的php框架

    本课以一个极简的PHP开发框架为案例,向您展示了一个PHP框架应该具有的基本功能,以及具体的实现方法,让您快速对PHP开发框架的底层实现有一个清楚的认识,为以后学习其实的开发框架打下坚实的基础。

    独孤九贱(3)_JavaScript视频教程

    javascript是运行在浏览器上的脚本语言,连续多年,被评为全球最受欢迎的编程语言。是前端开发必备三大法器中,最具杀伤力。如果前端开发是降龙十八掌,好么javascript就是第18掌:亢龙有悔。...

    直播实录:PHP魔鬼训练营[从零开始制作个人博客]

    本站9月直播课已经结束,本套教程是直播实录,没有报上名或者漏听学员福利来了,赶紧看看吧,说不定这里就有你的菜

    2018前端入门_HTML5

    轻松明快,简洁生动,让你快速走入HTML5的世界,体会语义化开发的魅力

    JavaScript极速入门_玉女心经系列

    JavaScript能够称得上是史上使用最广泛的编程语言,也是前端开发必须掌握的三技能之一:描述网页内容的HTML、描述网页样式的CSS以及描述网页行为的JavaScript。本章节将帮助大家迅速掌握...

    独孤九贱(7)_Bootstrap视频教程

    Bootstrap 是最受欢迎的 HTML、CSS 和 JS 框架,用于开发响应式布局、移动设备优先的 WEB 项目。为所有开发者、所有应用场景而设计,它让前端开发更快速、简单,所有开发者都能快速上手...

    PHP用户注册登录系统视频教程

    《php用户注册登录系统》主要介绍网站的登录注册功能,我们会从最简单的实现登录注册功能开始,增加验证码,cookie验证等,丰富网站的登录注册功能

    独孤九贱(2)_CSS视频教程

    《php.cn独孤九贱(2)-css视频教程》课程特色:php中文网原创幽默段子系列课程,以恶搞,段子为主题风格的php视频教程!轻松的教学风格,简短的教学模式,让同学们在不知不觉中,学会了CSS知识...

    PHP学生管理系统视频教程

    《PHP学生管理系统视频教程》主要给大家讲解了HTML,PHP,MySQL之间的相互协作,实现动态的网页显示和获取数据.

    独孤九贱(6)_jQuery视频教程

    jQuery是一个快速、简洁的JavaScript框架。设计的宗旨是“write Less,Do More”,即倡导写更少的代码,做更多的事情。它封装JavaScript常用的功能代码,提供一种简便的...

    弹指间学会HTML视频教程

    《弹指间学会HTML视频教程》从最基本的概念开始讲起,步步深入,带领大家学习HTML,了解各种常用标签的意义以及基本用法,学习HTML知识为以后的学习打下基础

    最新微信小程序开发视频教程

    《最新微信小程序开发视频教程》本节课程是由微趋道录制,讲述了如何申请一个微信小程序,以及开发中需要使用哪些工具,和需要注意哪些等。

    • 黄舟

      全栈工程师

    • 人生最曼妙的风景,竟是内心的淡定与从容!
    • 12001篇
      文章总数
    • 278
      文章总浏览数

    头条

    推荐视频教程

  • javascript初级视频教程
  • jquery 基础视频教程
  • javascript三级联动视频教程
  • 独孤九贱(3)_JavaScript视频教程
  • 独孤九贱(6)_jQuery视频教程
  • 最新更新