单源最短路径算法-Dijkstra-阿里云开发者社区

描述：

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

单源最短路径算法-Dijkstra

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

单源最短路径算法-Dijkstra

热门文章

最新文章

相关课程

相关电子书