文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

java实现最短路径算法之Dijkstra算法的示例

2023-05-31 00:49

关注

这篇文章主要介绍了java实现最短路径算法之Dijkstra算法的示例,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。

一、知识准备:

1、表示图的数据结构

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

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

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

java实现最短路径算法之Dijkstra算法的示例

java实现最短路径算法之Dijkstra算法的示例

从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是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的最短路。其中,满足上面两式的被称为最短路问题的互补松弛条件。

二、算法思想

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

算法初始有一个数组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实现最短路径算法之Dijkstra算法的示例

java实现最短路径算法之Dijkstra算法的示例  

三、java代码实现

public class Vertex implements Comparable<Vertex>{    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算法的示例”这篇文章对大家有帮助,同时也希望大家多多支持编程网,关注编程网行业资讯频道,更多相关知识等着你来学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯