描述：
1)算法思想原理：
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
2).算法描述：
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
Dijkstra算法：用于计算图中某一点到其他各点的最短路径。关于Dijkstra算法的说明可以参考 数据结构相关书籍。 为Dijkstra算法设计的类： 1. Node 节点类
2. Edge 边类 3. Graph 图类 4. Dijkstra Dijkstra算法类 --------------------------------------------------------------------------------------------------------------------------------- Node类： Java代码 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类： Java代码 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类： Java代码 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类： Java代码 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 相关资源：动态规划法实现最短路径问题java代码