问道鞭长莫及,易趣通,张雯心 李亮
本文实例为大家分享了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
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
浅析我对 String、StringBuilder、StringBuffer 的理解
使用IDEA搭建SSM框架的详细教程(spring + springMVC +MyBatis)
Springboot整合freemarker 404问题解决方案
引入mybatis-plus报 Invalid bound statement错误问题的解决方法
网友评论