Dijkstra算法:用于计算图中某一点到其他各点的最短路径。关于Dijkstra算法的说明可以参考 数据结构相关书籍。
为Dijkstra算法设计的类:
1. Node 节点类
2. Edge 边类
3. Graph 图类
4. Dijkstra Dijkstra算法类
3. Graph 图类
4. Dijkstra Dijkstra算法类
---------------------------------------------------------------------------------------------------------------------------------
Node类:
package com.sabrina.dijkstra; import java.util.ArrayList; import java.util.List; public class Node { // 节点编号 private String id; // 从当前节点出发的边的信息列表 private List outEdges; public Node(String id) { this.id = id; outEdges = new ArrayList(); } public void addOutEdge(Edge edge) { if(edge != null) outEdges.add(edge); } public String getId() { return id; } public void setId(String id) { this.id = id; } public List getOutEdges() { return outEdges; } public void setOutEdges(List outEdges) { this.outEdges = outEdges; } }
Edge类:
package com.sabrina.dijkstra; public class Edge { // 边的起始节点编号 private String startNodeID; // 边的末尾节点编号 private String endNodeID; // 边的权值 private double weight; public String getStartNodeID() { return startNodeID; } public void setStartNodeID(String startNodeID) { this.startNodeID = startNodeID; } public String getEndNodeID() { return endNodeID; } public void setEndNodeID(String endNodeID) { this.endNodeID = endNodeID; } public double getWeight() { return weight; } public void setWeight(double weight) { this.weight = weight; } }
Graph类:
package com.sabrina.dijkstra; import java.util.ArrayList; import java.util.List; public class Graph { // 图中的节点列表 public List nodeList = null; public Graph() { nodeList = new ArrayList(); } public List getNodeList() { return nodeList; } // initialize public void init() { // ************************ Node A *********************** Node aNode = new Node("A"); nodeList.add(aNode); // A -> B Edge a2bEdge = new Edge(); a2bEdge.setStartNodeID(aNode.getId()); a2bEdge.setEndNodeID("B"); a2bEdge.setWeight(10); aNode.addOutEdge(a2bEdge); // A -> C Edge a2cEdge = new Edge(); a2cEdge.setStartNodeID(aNode.getId()); a2cEdge.setEndNodeID("C"); a2cEdge.setWeight(20); aNode.addOutEdge(a2cEdge); // A -> E Edge a2eEdge = new Edge(); a2eEdge.setStartNodeID(aNode.getId()); a2eEdge.setEndNodeID("E"); a2eEdge.setWeight(30); aNode.addOutEdge(a2eEdge); // ************************ Node B *********************** Node bNode = new Node("B"); nodeList.add(bNode); // B -> C Edge b2cEdge = new Edge(); b2cEdge.setStartNodeID(bNode.getId()); b2cEdge.setEndNodeID("C"); b2cEdge.setWeight(5); bNode.addOutEdge(b2cEdge); // B -> E Edge b2eEdge = new Edge(); b2eEdge.setStartNodeID(bNode.getId()); b2eEdge.setEndNodeID("E"); b2eEdge.setWeight(10); bNode.addOutEdge(b2eEdge); // ************************ Node C *********************** Node cNode = new Node("C"); nodeList.add(cNode); // C -> D Edge c2dEdge = new Edge(); c2dEdge.setStartNodeID(cNode.getId()); c2dEdge.setEndNodeID("D"); c2dEdge.setWeight(30); cNode.addOutEdge(c2dEdge); // ************************ Node D *********************** Node dNode = new Node("D"); nodeList.add(dNode); // ************************ Node E *********************** Node eNode = new Node("E"); nodeList.add(eNode); // E -> D Edge e2dEdge = new Edge(); e2dEdge.setStartNodeID(eNode.getId()); e2dEdge.setEndNodeID("D"); e2dEdge.setWeight(20); eNode.addOutEdge(e2dEdge); } }
Dijkstra类:
package com.sabrina.dijkstra; import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.Map; public class Dijkstra { // 起始节点编号 private String startNodeID; // 未被处理的节点集合 private List sourceNodeIDList = null; // 已被处理的节点集合 private List desNodeIDList = null; // '节点编号' 和 '起始节点与当前节点之间的最短路径' 的映射关系 private Map nodeidShortestRouteMapping = null; // '节点编号' 和 '起始节点到当前节点之间的最短路径 的 上一跳节点编号' 的映射关系 private Map nodeidLastNodeidMapping = null; // '节点编号' 和 '节点对象'的 映射关系 private Map idNodeMapping = null; public Dijkstra(Graph graph, String startNodeID) { this.startNodeID = startNodeID; // 初始化 sourceNodeIDList = new ArrayList(); desNodeIDList = new ArrayList(); nodeidShortestRouteMapping = new HashMap(); nodeidLastNodeidMapping = new HashMap(); idNodeMapping = new HashMap(); for(Node node : graph.getNodeList()) { if(node.getId().equals(startNodeID)) { desNodeIDList.add(startNodeID); // 起始节点到起始节点的最短路径长度为0 nodeidShortestRouteMapping.put(startNodeID, 0d); } else { sourceNodeIDList.add(node.getId()); // 非起始节点到起始节点的最短路径长度为 '无穷大' nodeidShortestRouteMapping.put(node.getId(), Double.MAX_VALUE); } // 设置到节点最短路径的上一跳节点为'null' nodeidLastNodeidMapping.put(node.getId(), null); idNodeMapping.put(node.getId(), node); } } public void start() { Node nextNode = null; Node currentNode = null; String nextNodeID = ""; do { if(nextNode == null) { currentNode = idNodeMapping.get(startNodeID); } else { currentNode = nextNode; } nextNodeID = getNextNode(currentNode); nextNode = idNodeMapping.get(nextNodeID); System.out.println("nextNode.id:" + nextNode.getId()); sourceNodeIDList.remove(nextNode.getId()); System.out.println("sourceNodeIDList:" + sourceNodeIDList.toString()); } while(sourceNodeIDList.size() > 0); } public String getNextNode(Node currentNode) { System.out.println("============= currentNode.id: " + currentNode.getId() + " ============="); double shortestPath = Double.MAX_VALUE; String nextNodeID = ""; // 遍历从当前节点出发的邻接节点 for(Edge nextEdge : currentNode.getOutEdges()) { System.out.println("nextEdge.endNodeid:" + nextEdge.getEndNodeID()); // 判断 '经过当前节点至邻接节点的距离' < '之前记录的从源节点出发到邻接节点的距离' if((nextEdge.getWeight() + nodeidShortestRouteMapping.get(currentNode.getId())) < nodeidShortestRouteMapping.get(nextEdge.getEndNodeID())) { // 更新路由表 nodeidShortestRouteMapping.put(nextEdge.getEndNodeID(), nextEdge.getWeight() + nodeidShortestRouteMapping.get(currentNode.getId())); nodeidLastNodeidMapping.put(nextEdge.getEndNodeID(), currentNode.getId()); } } // 从未被处理过的节点集合中,取出权值最小的节点 for(String nodeID : sourceNodeIDList) { if(nodeidShortestRouteMapping.get(nodeID) < shortestPath) { shortestPath = nodeidShortestRouteMapping.get(nodeID); nextNodeID = nodeID; } } if(sourceNodeIDList.size() == 1) // 从未被处理过的节点集合中,取出最后一个节点 return sourceNodeIDList.get(0); return nextNodeID; } public Map getNodeidShortestRouteMapping() { return nodeidShortestRouteMapping; } public Map getNodeidLastNodeidMapping() { return nodeidLastNodeidMapping; } public static void main(String[] args) { Graph graph = new Graph(); graph.init(); Dijkstra dijkstra = new Dijkstra(graph, "A"); dijkstra.start(); // 打印最终的路由表 Iterator it = dijkstra.getNodeidShortestRouteMapping().keySet().iterator(); while(it.hasNext()) { String id = it.next(); System.out.println("nodeId: " + id + ", shortest length: " + dijkstra.getNodeidShortestRouteMapping().get(id) + ", last nodeId: " + dijkstra.getNodeidLastNodeidMapping().get(id)); } } }
最终执行结果
============= currentNode.id: A =============
nextEdge.endNodeid:B
nextEdge.endNodeid:C
nextEdge.endNodeid:E
nextNode.id:B
sourceNodeIDList:[C, D, E]
============= currentNode.id: B =============
nextEdge.endNodeid:C
nextEdge.endNodeid:E
nextNode.id:C
sourceNodeIDList:[D, E]
============= currentNode.id: C =============
nextEdge.endNodeid:D
nextNode.id:E
sourceNodeIDList:[D]
============= currentNode.id: E =============
nextEdge.endNodeid:D
nextNode.id:D
sourceNodeIDList:[]
nodeId: D, shortest length: 40.0, last nodeId: E
nodeId: E, shortest length: 20.0, last nodeId: B
nodeId: A, shortest length: 0.0, last nodeId: null
nodeId: B, shortest length: 10.0, last nodeId: A
nodeId: C, shortest length: 15.0, last nodeId: B
nextEdge.endNodeid:B
nextEdge.endNodeid:C
nextEdge.endNodeid:E
nextNode.id:B
sourceNodeIDList:[C, D, E]
============= currentNode.id: B =============
nextEdge.endNodeid:C
nextEdge.endNodeid:E
nextNode.id:C
sourceNodeIDList:[D, E]
============= currentNode.id: C =============
nextEdge.endNodeid:D
nextNode.id:E
sourceNodeIDList:[D]
============= currentNode.id: E =============
nextEdge.endNodeid:D
nextNode.id:D
sourceNodeIDList:[]
nodeId: D, shortest length: 40.0, last nodeId: E
nodeId: E, shortest length: 20.0, last nodeId: B
nodeId: A, shortest length: 0.0, last nodeId: null
nodeId: B, shortest length: 10.0, last nodeId: A
nodeId: C, shortest length: 15.0, last nodeId: B
PS:如有写的不对的,敬请纠正~
相关推荐
Dijkstra算法通过计算起始顶点到其他顶点的最短路径来解决单源最短路径问题。在示例代码中,我们使用数组distance来记录起始顶点到其他顶点的最短距离。 首先,我们初始化所有顶点的距离为无穷大(用Integer.MAX_...
使用java实现dijkstra算法的最短路径,附有简单的例子。
java实现的DIJKSTRA,可以给出图中一点到指定的另一点其中的一个最短路径
dijkstra算法,寻一个节点到其它所有节点的最短路径,java实现
Dijkstra算法 用Java实现Dijkstra的算法。
以下是Java语言实现Dijkstra算法的一个简单示例,这个示例假设你有一个图的邻接矩阵表示,并且所有边的权重都是正数。 代码定义了一个DijkstraExample类,其中包含了Dijkstra算法的实现。dijkstra方法接受一个图的...
Dijkstra 求任意两个点的最短路径算法
NULL 博文链接:https://feng2010.iteye.com/blog/1175366
本资源用java实现,完成的是基于Dijkstra路由算法的路由软件实现。
java算法分析与设计之单源最短路径(Dijkstra算法)源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络...
Dijkstra算法的java实现方式及优化
主要介绍了基于Java实现的Dijkstra算法示例,一个比较典型的算法示例,需要的朋友可以参考下
路径规划算法中,Dijkstra算法本质上还是广度优先搜索的思想,所以其效率较低,搜索的大多为无用的路径。为解决Dijkstra算法效率低的问题,A*算法作为一种启发式算法被提出。 因此,该资源将为自动驾驶轨迹规划的...
用堆优化的dijkstra,接口为邻接链表。
带权图的多种算法(有向图,无向图,Dijkstra算法,到每个顶点的最短距离,佛洛依德算法(Floyd),找出每对顶点的最短路径,带权重无向图最小生成树,prim算法,Kruskal算法求最小生成树)java实现, 有注释,简单...
Dijkstra算法的java实现方式及优化.pdf