当前位置: 萬仟网 > IT编程>开发语言>Java > java实现Dijkstra算法

java实现Dijkstra算法

2020年06月23日  | 萬仟网IT编程  | 我要评论

本文实例为大家分享了java实现dijkstra算法的具体代码,供大家参考,具体内容如下

1 问题描述

何为dijkstra算法?

dijkstra算法功能:给出加权连通图中一个顶点,称之为起点,找出起点到其它所有顶点之间的最短距离。

dijkstra算法思想:采用贪心法思想,进行n-1次查找(ps:n为加权连通图的顶点总个数,除去起点,则剩下n-1个顶点),第一次进行查找,找出距离起点最近的一个顶点,标记为已遍历;下一次进行查找时,从未被遍历中的顶点寻找距离起点最近的一个顶点, 标记为已遍历;直到n-1次查找完毕,结束查找,返回最终结果。

2 解决方案

2.1 使用dijkstra算法得到最短距离示例

此处借用文末参考资料1博客中一个插图(ps:个人感觉此图描述简单易懂):

2.2 具体编码

dijkstra复杂度是o(n^2),如果用binary heap优化可以达到o((e+n)logn),用fibonacci heap可以优化到o(nlogn+e) 。

注意,dijkstra算法只能应用于不含负权值的图。因为在大多数应用中这个条件都满足,所以这种局限性并没有影响dijkstra算法的广泛应用。

其次,大家要注意把dijkstra算法与寻找最小生成树的prim算法区分开来。两者都是运行贪心法思想,但是dijkstra算法是比较路径的长度,所以必须把起点到相应顶点之间的边的权重相加,而prim算法则是直接比较相应边给定的权重。

下面的代码时间复杂度为o(n^2),代码中所用图为2.1使用dijkstra算法得到最短距离示例中所给的图。

package com.liuzhen.chapter9;

public class dijkstra {
  /*
   * 参数adjmatrix:为图的权重矩阵,权值为-1的两个顶点表示不能直接相连
   * 函数功能:返回顶点0到其它所有顶点的最短距离,其中顶点0到顶点0的最短距离为0
   */
  public int[] getshortestpaths(int[][] adjmatrix) {
    int[] result = new int[adjmatrix.length];  //用于存放顶点0到其它顶点的最短距离
    boolean[] used = new boolean[adjmatrix.length]; //用于判断顶点是否被遍历
    used[0] = true; //表示顶点0已被遍历
    for(int i = 1;i < adjmatrix.length;i++) {
      result[i] = adjmatrix[0][i];
      used[i] = false;
    }
  
    for(int i = 1;i < adjmatrix.length;i++) {
      int min = integer.max_value;  //用于暂时存放顶点0到i的最短距离,初始化为integer型最大值
      int k = 0;
      for(int j = 1;j < adjmatrix.length;j++) { //找到顶点0到其它顶点中距离最小的一个顶点
        if(!used[j] && result[j] != -1 && min > result[j]) {
          min = result[j];
          k = j;
        }
      }
      used[k] = true;  //将距离最小的顶点,记为已遍历
      for(int j = 1;j < adjmatrix.length;j++) { //然后,将顶点0到其它顶点的距离与加入中间顶点k之后的距离进行比较,更新最短距离
        if(!used[j]) { //当顶点j未被遍历时
          //首先,顶点k到顶点j要能通行;这时,当顶点0到顶点j的距离大于顶点0到k再到j的距离或者顶点0无法直接到达顶点j时,更新顶点0到顶点j的最短距离
          if(adjmatrix[k][j] != -1 && (result[j] > min + adjmatrix[k][j] || result[j] == -1))
            result[j] = min + adjmatrix[k][j];
        }
      }
    }
    return result;
  }
  
  public static void main(string[] args) {
    dijkstra test = new dijkstra();
    int[][] adjmatrix = {{0,6,3,-1,-1,-1},
        {6,0,2,5,-1,-1},
        {3,2,0,3,4,-1},
        {-1,5,3,0,2,3},
        {-1,-1,4,2,0,5},
        {-1,-1,-1,3,5,0}};
    int[] result = test.getshortestpaths(adjmatrix);
    system.out.println("顶点0到图中所有顶点之间的最短距离为:");
    for(int i = 0;i < result.length;i++) 
      system.out.print(result[i]+" ");
  }
}

运行结果:

顶点0到图中所有顶点之间的最短距离为:
0 5 3 6 7 9

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持萬仟网。

如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复

相关文章:

验证码:
Copyright © 2020  萬仟网 保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com