无向图的最短路径求解算法之—

>> 欢迎您客人: 登录 | 注册 | 在线 | 搜索 | 风格 | 帮助 | 统计 | 文章

返回首页

>>分享数据结构和算法相关的知识和技术

书籍支持

卫琴直播

品书摘要

在线测试

资源下载

联系我们

Java技术网站 → 『 Java开发技术』 → 『数据结构和算法专题』 → 无向图的最短路径求解算法之——Dijkstra算法

您是本文章第 25011 个阅读者

* 贴子主题: 无向图的最短路径求解算法之——Dijkstra算法

点赞(0) 收藏

作者:flybird 发表时间：2020-03-15 21:20:39

消息

查看

搜索

好友

邮件

复制

引用

刚开始学dijkstra算法的时候，写过一篇关于dijkstra算法的博客，留下的QQ，结果很多人来询问。

后来，发现那个代码写得实在是太难看了，于是把代码重新整理了一下，贴上来吧。数据还是http://sbp810050504.blog.51cto.com/2799422/690803 里面的数据。

import java.util.Arrays;
public class Dijkstra {
private static final int inf=Integer.MAX_VALUE; //表示两个点之间无法直接连通
public static int [] dijkstra( int [][] graph, int n, int u){
int dist[]= new int [n];
boolean s[]= new boolean [n];
Arrays.fill(s, false );
Arrays.fill(dist, inf);
int min,v;
for ( int i= 0 ;i<n;i++){
dist[i]=graph[u][i];
}
s[u]= true ;
while ( true ){
min=inf;v=- 1 ;
//找到最小的dist
for ( int i= 0 ;i<n;i++){
if (!s[i]){
if (dist[i]<min){min=dist[i];v=i;}
}
}
if (v==- 1 ) break ; //找不到更短的路径了
//更新最短路径
s[v]= true ;
for ( int i= 0 ;i<n;i++){
if (!s[i]&&
graph[v][i]!=inf&&
dist[v]+graph[v][i]<dist[i]){
dist[i]=dist[v]+graph[v][i];
}
}
}
return dist;
}
public static void main(String[] args) {
int [][] W = {
{ 0 , 1 , 4 , inf, inf, inf },
{ 1 , 0 , 2 , 7 , 5 , inf },
{ 4 , 2 , 0 , inf, 1 , inf },
{ inf, 7 , inf, 0 , 3 , 2 },
{ inf, 5 , 1 , 3 , 0 , 6 },
{ inf, inf, inf, 2 , 6 , 0 } };
int [] dist=dijkstra(W, 6 , 0 );
for ( int i : dist) {
System.out.print(i+ " " );
}
System.out.println();
}
}

----------------------------
原文链接:https://blog.51cto.com/sbp810050504/1163565

程序猿的技术大观园：www.javathinker.net

[这个贴子最后由 flybird 在 2020-03-16 11:30:47 重新编辑]

Java精品书籍推荐