类似于gbt小组:一个Dijkstra算法的完整Java程序实现,算法初学者必看! - brokencar的专栏 - CSDNBlog
来源:百度文库 编辑:中财网 时间:2024/04/25 18:26:34
public class Dijkstra {
public static void main(String[] args) {
new Dijkstra().use();
}
public void use(){
new Dijkstra().dijkstra(0, a, dist, prev);
for (int i = 0; i < dist.length; i++) {
System.out.print(dist[i]+" ");
}
}
//单元最短路径问题的Dijkstra算法
public void dijkstra(int v ,float[][] a, float[] dist,int[] prev){
int n = dist.length - 1 ;
if(v < 0 || v > n-1) return;
boolean[] s = new boolean[n+1];
//初始化
for(int i = 1; i <= n; i++){
dist[i] = a[v][i];
s[i] = false;
if(dist[i] == Float.MAX_VALUE){
prev[i] = 0;
} else {
prev[i] = v;
}
}
dist[v] = 0;
s[v] = true;
for(int i = 1; i < n; i++){
float temp = Float.MAX_VALUE;
int u = v;
for(int j = 1; j <= n; j++){
if((!s[j]) && (dist[j] < temp)){
u = j;
temp = dist[j];
}
}
s[u] = true; //找到了第一个并入S的节点
for(int j = 1; j <= n; j++){
if((!s[j]) && (a[u][j] < Float.MAX_VALUE)){
float newdist = dist[u] + a[u][j];
if(newdist < dist[j]){
//dist[j] 减少
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
private float[][] a = {
{0,10,max,30,100},
{max,0,50,max,max},
{max,max,0,max,10},
{max,max,20,0,60},
{max,max,max,max,0}
};
private float[] dist = new float[5];
private int[] prev = new int[5];
public static final float max = Float.MAX_VALUE;
}
public static void main(String[] args) {
new Dijkstra().use();
}
public void use(){
new Dijkstra().dijkstra(0, a, dist, prev);
for (int i = 0; i < dist.length; i++) {
System.out.print(dist[i]+" ");
}
}
//单元最短路径问题的Dijkstra算法
public void dijkstra(int v ,float[][] a, float[] dist,int[] prev){
int n = dist.length - 1 ;
if(v < 0 || v > n-1) return;
boolean[] s = new boolean[n+1];
//初始化
for(int i = 1; i <= n; i++){
dist[i] = a[v][i];
s[i] = false;
if(dist[i] == Float.MAX_VALUE){
prev[i] = 0;
} else {
prev[i] = v;
}
}
dist[v] = 0;
s[v] = true;
for(int i = 1; i < n; i++){
float temp = Float.MAX_VALUE;
int u = v;
for(int j = 1; j <= n; j++){
if((!s[j]) && (dist[j] < temp)){
u = j;
temp = dist[j];
}
}
s[u] = true; //找到了第一个并入S的节点
for(int j = 1; j <= n; j++){
if((!s[j]) && (a[u][j] < Float.MAX_VALUE)){
float newdist = dist[u] + a[u][j];
if(newdist < dist[j]){
//dist[j] 减少
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
private float[][] a = {
{0,10,max,30,100},
{max,0,50,max,max},
{max,max,0,max,10},
{max,max,20,0,60},
{max,max,max,max,0}
};
private float[] dist = new float[5];
private int[] prev = new int[5];
public static final float max = Float.MAX_VALUE;
}
关于Dijkstra 算法的一个问题
dijkstra算法的改进程序
dijkstra算法的改进程序
dijkstra算法是什么?
Dijkstra算法算最短路径
怎么编程实现求图最短路的Dijkstra算法
dijkstra算法解决“狼羊菜”问题
求C++的dijkstra算法或者floyd算法的参考源代码
求助Dijkstra迪杰的VC++算法 毕业设计 急~~~跪求
一个关于JAVA数据结构与算法的问题
求java阶乘的算法
JAVA算法
des加密解密算法的完整程序
m树索引算法的java实现
C与JAVA的区别,特别是算法
java应用bm算法的字符串匹配
用JAVA写出冒泡排序的算法
用JAVA实现的Apriori算法
“银行家算法”是怎样的一个算法?
谁有完整的<张孝祥的JAVA视频教程>啊?或告诉我一个地址。
一个完整的JAVA源文件的构成包括哪几个部分?
java下如何判断一个汉字是完整的,而不是半个汉字?
java海龟图算法
java海龟图算法