package sinboy.datastructure;
import java.util.ArrayList;
public class Dijkstra ...{
static ArrayList<Side> map = null;
static ArrayList<Integer> redAgg = null;
static ArrayList<Integer> blueAgg = null;
static Side[] parents = null;
public static void main(String[] args) ...{
// 初始化顶点集
int[] nodes = ...{ 0, 1, 3, 2, 4, 5,6 };
// 初始化有向权重图
map = new ArrayList<Side>();
map.add(new Side(0, 1, 10));
map.add(new Side(0, 3, 30));
map.add(new Side(0, 4, 100));
map.add(new Side(1, 2, 50));
map.add(new Side(2, 4, 10));
map.add(new Side(3, 2, 20));
map.add(new Side(3, 4, 60));
map.add(new Side(4, 5, 50));
map.add(new Side(3, 5, 60));
map.add(new Side(5, 6, 10));
map.add(new Side(3, 6, 80));
// 初始化已知最短路径的顶点集,即红点集,只加入顶点0
redAgg = new ArrayList<Integer>();
redAgg.add(nodes[0]);
// 初始化未知最短路径的顶点集,即蓝点集
blueAgg = new ArrayList<Integer>();
for (int i = 1; i < nodes.length; i++)
blueAgg.add(nodes[i]);
// 初始化每个顶点在最短路径中的父结点,及它们之间的权重,权重-1表示无连通
parents = new Side[nodes.length];
parents[0] = new Side(-1, nodes[0], 0);
for (int i = 0; i < blueAgg.size(); i++) ...{
int n = blueAgg.get(i);
parents[i + 1] = new Side(nodes[0], n, getWeight(nodes[0], n));
}
// 找从蓝点集中找出权重最小的那个顶点,并把它加入到红点集中
while (blueAgg.size() > 0) ...{
MinShortPath msp = getMinSideNode();
if(msp.getWeight()==-1)
msp.outputPath(nodes[0]);
else
msp.outputPath();
int node = msp.getLastNode();
redAgg.add(node);
// 如果因为加入了新的顶点,而导致蓝点集中的顶点的最短路径减小,则要重要设置
setWeight(node);
}
}
/** *//**
* 得到一个节点的父节点
*
* @param parents
* @param node
* @return
*/
public static int getParent(Side[] parents, int node) ...{
if (parents != null) ...{
for (Side nd : parents) ...{
if (nd.getNode() == node) ...{
return nd.getPreNode();
}
}
}
return -1;
}
/** *//**
* 重新设置蓝点集中剩余节点的最短路径长度
*
* @param preNode
* @param map
* @param blueAgg
*/
public static void setWeight(int preNode) ...{
if (map != null && parents != null && blueAgg != null) ...{
for (int node : blueAgg) ...{
MinShortPath msp=getMinPath(node);
int w1 = msp.getWeight();
if (w1 == -1)
continue;
for (Side n : parents) ...{
if (n.getNode() == node) ...{
if (n.getWeight() == -1 || n.getWeight() > w1) ...{
n.setWeight(w1);
n.setPreNode(preNode);//重新设置顶点的父顶点
break;
}
}
}
}
}
}
/** *//**
* 得到两点节点之间的权重
*
* @param map
* @param preNode
* @param node
* @return
*/
public static int getWeight(int preNode, int node) ...{
if (map != null) ...{
for (Side s : map) ...{
if (s.getPreNode() == preNode && s.getNode() == node)
return s.getWeight();
}
}
return -1;
}
/** *//**
* 从蓝点集合中找出路径最小的那个节点
*
* @param map
* @param blueAgg
* @return
*/
public static MinShortPath getMinSideNode() ...{
MinShortPath minMsp = null;
if (blueAgg.size() > 0) ...{
int index = 0;
for (int j = 0; j < blueAgg.size(); j++) ...{
MinShortPath msp = getMinPath(blueAgg.get(j));
if (minMsp == null || msp.getWeight()!=-1 && msp.getWeight() < minMsp.getWeight()) ...{
minMsp = msp;
index = j;
}
}
blueAgg.remove(index);
}
return minMsp;
}
/** *//**
* 得到某一节点的最短路径(实际上可能有多条,现在只考虑一条)
* @param node
* @return
*/
public static MinShortPath getMinPath(int node) ...{
MinShortPath msp = new MinShortPath(node);
if (parents != null && redAgg != null) ...{
for (int i = 0; i < redAgg.size(); i++) ...{
MinShortPath tempMsp = new MinShortPath(node);
int parent = redAgg.get(i);
int curNode = node;
while (parent > -1) ...{
int weight = getWeight(parent, curNode);
if (weight > -1) ...{
tempMsp.addNode(parent);
tempMsp.addWeight(weight);
curNode = parent;
parent = getParent(parents, parent);
} else
break;
}
if (msp.getWeight() == -1 || tempMsp.getWeight()!=-1 && msp.getWeight() > tempMsp.getWeight())
msp = tempMsp;
}
}
return msp;
}
}
/** *//**
* 图中的有向边,包括节点名及他的一个前向节点名,和它们之间的权重
*
*/
class Side ...{
private int preNode; // 前向节点
private int node;// 后向节点
private int weight;// 权重
public Side(int preNode, int node, int weight) ...{
this.preNode = preNode;
this.node = node;
this.weight = weight;
}
public int getPreNode() ...{
return preNode;
}
public void setPreNode(int preNode) ...{
this.preNode = preNode;
}
public int getNode() ...{
return node;
}
public void setNode(int node) ...{
this.node = node;
}
public int getWeight() ...{
return weight;
}
public void setWeight(int weight) ...{
this.weight = weight;
}
}
class MinShortPath ...{
private ArrayList<Integer> nodeList;// 最短路径集
private int weight;// 最短路径
public MinShortPath(int node) ...{
nodeList = new ArrayList<Integer>();
nodeList.add(node);
weight = -1;
}
public ArrayList<Integer> getNodeList() ...{
return nodeList;
}
public void setNodeList(ArrayList<Integer> nodeList) ...{
this.nodeList = nodeList;
}
public void addNode(int node) ...{
if (nodeList == null)
nodeList = new ArrayList<Integer>();
nodeList.add(0, node);
}
public int getLastNode() ...{
int size = nodeList.size();
return nodeList.get(size - 1);
}
public int getWeight() ...{
return weight;
}
public void setWeight(int weight) ...{
this.weight = weight;
}
public void outputPath() ...{
outputPath(-1);
}
public void outputPath(int srcNode) ...{
String result = "[";
if (srcNode != -1)
nodeList.add(srcNode);
for (int i = 0; i < nodeList.size(); i++) ...{
result += "" + nodeList.get(i);
if (i < nodeList.size() - 1)
result += ",";
}
result += "]:" + weight;
System.out.println(result);
}
public void addWeight(int w) ...{
if (weight == -1)
weight = w;
else
weight += w;
}
}
运行结果如下:
[0,1]:10
[0,3]:30
[0,3,2]:50
[0,3,2,4]:60
[0,3,5]:90
[0,3,5,6]:100
来自【http://www.java3z.com/cwbwebhome/article/article2/2784.html?id=1314】
import java.util.ArrayList;
public class Dijkstra ...{
static ArrayList<Side> map = null;
static ArrayList<Integer> redAgg = null;
static ArrayList<Integer> blueAgg = null;
static Side[] parents = null;
public static void main(String[] args) ...{
// 初始化顶点集
int[] nodes = ...{ 0, 1, 3, 2, 4, 5,6 };
// 初始化有向权重图
map = new ArrayList<Side>();
map.add(new Side(0, 1, 10));
map.add(new Side(0, 3, 30));
map.add(new Side(0, 4, 100));
map.add(new Side(1, 2, 50));
map.add(new Side(2, 4, 10));
map.add(new Side(3, 2, 20));
map.add(new Side(3, 4, 60));
map.add(new Side(4, 5, 50));
map.add(new Side(3, 5, 60));
map.add(new Side(5, 6, 10));
map.add(new Side(3, 6, 80));
// 初始化已知最短路径的顶点集,即红点集,只加入顶点0
redAgg = new ArrayList<Integer>();
redAgg.add(nodes[0]);
// 初始化未知最短路径的顶点集,即蓝点集
blueAgg = new ArrayList<Integer>();
for (int i = 1; i < nodes.length; i++)
blueAgg.add(nodes[i]);
// 初始化每个顶点在最短路径中的父结点,及它们之间的权重,权重-1表示无连通
parents = new Side[nodes.length];
parents[0] = new Side(-1, nodes[0], 0);
for (int i = 0; i < blueAgg.size(); i++) ...{
int n = blueAgg.get(i);
parents[i + 1] = new Side(nodes[0], n, getWeight(nodes[0], n));
}
// 找从蓝点集中找出权重最小的那个顶点,并把它加入到红点集中
while (blueAgg.size() > 0) ...{
MinShortPath msp = getMinSideNode();
if(msp.getWeight()==-1)
msp.outputPath(nodes[0]);
else
msp.outputPath();
int node = msp.getLastNode();
redAgg.add(node);
// 如果因为加入了新的顶点,而导致蓝点集中的顶点的最短路径减小,则要重要设置
setWeight(node);
}
}
/** *//**
* 得到一个节点的父节点
*
* @param parents
* @param node
* @return
*/
public static int getParent(Side[] parents, int node) ...{
if (parents != null) ...{
for (Side nd : parents) ...{
if (nd.getNode() == node) ...{
return nd.getPreNode();
}
}
}
return -1;
}
/** *//**
* 重新设置蓝点集中剩余节点的最短路径长度
*
* @param preNode
* @param map
* @param blueAgg
*/
public static void setWeight(int preNode) ...{
if (map != null && parents != null && blueAgg != null) ...{
for (int node : blueAgg) ...{
MinShortPath msp=getMinPath(node);
int w1 = msp.getWeight();
if (w1 == -1)
continue;
for (Side n : parents) ...{
if (n.getNode() == node) ...{
if (n.getWeight() == -1 || n.getWeight() > w1) ...{
n.setWeight(w1);
n.setPreNode(preNode);//重新设置顶点的父顶点
break;
}
}
}
}
}
}
/** *//**
* 得到两点节点之间的权重
*
* @param map
* @param preNode
* @param node
* @return
*/
public static int getWeight(int preNode, int node) ...{
if (map != null) ...{
for (Side s : map) ...{
if (s.getPreNode() == preNode && s.getNode() == node)
return s.getWeight();
}
}
return -1;
}
/** *//**
* 从蓝点集合中找出路径最小的那个节点
*
* @param map
* @param blueAgg
* @return
*/
public static MinShortPath getMinSideNode() ...{
MinShortPath minMsp = null;
if (blueAgg.size() > 0) ...{
int index = 0;
for (int j = 0; j < blueAgg.size(); j++) ...{
MinShortPath msp = getMinPath(blueAgg.get(j));
if (minMsp == null || msp.getWeight()!=-1 && msp.getWeight() < minMsp.getWeight()) ...{
minMsp = msp;
index = j;
}
}
blueAgg.remove(index);
}
return minMsp;
}
/** *//**
* 得到某一节点的最短路径(实际上可能有多条,现在只考虑一条)
* @param node
* @return
*/
public static MinShortPath getMinPath(int node) ...{
MinShortPath msp = new MinShortPath(node);
if (parents != null && redAgg != null) ...{
for (int i = 0; i < redAgg.size(); i++) ...{
MinShortPath tempMsp = new MinShortPath(node);
int parent = redAgg.get(i);
int curNode = node;
while (parent > -1) ...{
int weight = getWeight(parent, curNode);
if (weight > -1) ...{
tempMsp.addNode(parent);
tempMsp.addWeight(weight);
curNode = parent;
parent = getParent(parents, parent);
} else
break;
}
if (msp.getWeight() == -1 || tempMsp.getWeight()!=-1 && msp.getWeight() > tempMsp.getWeight())
msp = tempMsp;
}
}
return msp;
}
}
/** *//**
* 图中的有向边,包括节点名及他的一个前向节点名,和它们之间的权重
*
*/
class Side ...{
private int preNode; // 前向节点
private int node;// 后向节点
private int weight;// 权重
public Side(int preNode, int node, int weight) ...{
this.preNode = preNode;
this.node = node;
this.weight = weight;
}
public int getPreNode() ...{
return preNode;
}
public void setPreNode(int preNode) ...{
this.preNode = preNode;
}
public int getNode() ...{
return node;
}
public void setNode(int node) ...{
this.node = node;
}
public int getWeight() ...{
return weight;
}
public void setWeight(int weight) ...{
this.weight = weight;
}
}
class MinShortPath ...{
private ArrayList<Integer> nodeList;// 最短路径集
private int weight;// 最短路径
public MinShortPath(int node) ...{
nodeList = new ArrayList<Integer>();
nodeList.add(node);
weight = -1;
}
public ArrayList<Integer> getNodeList() ...{
return nodeList;
}
public void setNodeList(ArrayList<Integer> nodeList) ...{
this.nodeList = nodeList;
}
public void addNode(int node) ...{
if (nodeList == null)
nodeList = new ArrayList<Integer>();
nodeList.add(0, node);
}
public int getLastNode() ...{
int size = nodeList.size();
return nodeList.get(size - 1);
}
public int getWeight() ...{
return weight;
}
public void setWeight(int weight) ...{
this.weight = weight;
}
public void outputPath() ...{
outputPath(-1);
}
public void outputPath(int srcNode) ...{
String result = "[";
if (srcNode != -1)
nodeList.add(srcNode);
for (int i = 0; i < nodeList.size(); i++) ...{
result += "" + nodeList.get(i);
if (i < nodeList.size() - 1)
result += ",";
}
result += "]:" + weight;
System.out.println(result);
}
public void addWeight(int w) ...{
if (weight == -1)
weight = w;
else
weight += w;
}
}
运行结果如下:
[0,1]:10
[0,3]:30
[0,3,2]:50
[0,3,2,4]:60
[0,3,5]:90
[0,3,5,6]:100
来自【http://www.java3z.com/cwbwebhome/article/article2/2784.html?id=1314】
相关推荐
java算法分析与设计之单源最短路径(Dijkstra算法)源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络...
NULL 博文链接:https://128kj.iteye.com/blog/1678532
最短路径算法java 单源点最短路径Dijkstra算法的JAVA实现
java单源最短路径(贪心算法) public class TheShortestWay { static int MAX_SIZE = 6; public static void dijkstra(int v, float[][] a, float[] dist, int[] prev) { int n = dist.length - 1; if (v ||...
数据结构课程实践:1. 问题描述: 以顶点表示校平面图中各景点,要有景点名称、代号、简介等信息;以边表示路径,存放路径长度等...(2)解决单源点最短路径问题;(3)任意两个景点之间的最短路径。 我用java实现的
由Dijkstra贪心算法实现,设置顶点集合实现贪心扩充直到找到源点到所有顶点的路径长度;用dist数组记录当前从源到顶点的最短特殊路径长度
NULL 博文链接:https://tianyalinfeng.iteye.com/blog/1579525
Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的...
主要为大家详细介绍了java使用Dijkstra算法实现单源最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
•实现了Dijkstra的“单源最短路径”算法,以查找和打印无向图中任意两个给定节点之间的最短路径 •通过使用斐波那契堆来存储该图,优化了算法的运行时复杂度 第2部分:路由方案: •对于网络中的每个路由器,借助...
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业...
Dijkstra算法通过计算起始顶点到其他顶点的最短路径来解决单源最短路径问题。在示例代码中,我们使用数组distance来记录起始顶点到其他顶点的最短距离。 首先,我们初始化所有顶点的距离为无穷大(用Integer.MAX_...
迪杰斯特拉算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都...
Thorup发现了第一个确定性算法,用于解决线性时间和空间中具有正整数权重的无向图的经典单源最短路径问题。 该算法需要一个层次化的存储桶结构来标识必须访问顶点的顺序,而又不会破坏该时间范围,从而避免了...
一个简单的Java库,用于解决图形单源最短路径问题,这在数学或算法难题中很常见。 包括的示例应用程序。 基本用法 Dijkstra算法的主要代码在spdijklib模块内。 客户端应为ProblemState,ProblemStateFactory和...
我邀请您下载文件 Dijkstra-Maze-Game.jar 并尝试一下。 脚步: 1 / 加载一个已保存的迷宫或创建一个新迷宫。 2 / 键入“E”(空)或“W”(墙)以移除或设置实心块来构建地图。 3 / 通过点击选择一个方块来...
该项目旨在测量最著名的单源最短路径算法之一,Dijkstra 最短路径算法的不同实现的性能。 我正在考虑使用现有的斐波那契堆的开源实现的具有二元堆和优先级队列的简单优先队列和斐波那契堆类型实现。 我在这个实验中...
单源最短路径(Dijkstra) 全源最短路径(Floyd Warshall) Prim 的 MST 克鲁斯卡尔的 MST 拓扑排序(例如用于确定多模块项目中的项目构建顺序) 约翰逊算法 图中的连接点 图中的桥梁 检测图中的循环 11.a Using BFS...
实验五:最短路径算法一、实验目的(1)理解路径松驰技术的思想(2)掌握迪杰斯特拉算法(Dijkstra)的基本思想二、实验内容实现单源最短路经的迪杰斯特拉算法
·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地将注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...